leetcode.272 Closest Binary Search

dfs && stack + merge sort mothodology for the optimal solution

  • Analysis
    Implement two stack, one store the value less than target in increase order by inorder dfs.

like the root = [4, 2, 5, 1, 3], target = 3.3 => stack1: 1, 2, 3(top); stack2: 4, 5(top)

so the inorder basically has two version:

  • right part, which get larger value. skip small value
1
2
3
4
5
6
7
8
9
private void inorder1(TreeNode root, double target, Stack<Integer> stack){
	if(root==null) return;
	//dfs traversal the right path
	inorder1(root.right, target, stack);
	// if the root value less then target, no need to go deeper since it is bst
	if(root.val <= target) return;
	stack.push(root.val);
	inorder1(root.left, target, stack);
}

  • left part, get the small part, skip the bigger one.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    	private void inorder2(TreeNode root, double target, Stack<Integer> stack){
    	if(root==null) return;
    	//dfs traversal the right path
    	inorder1(root.left, target, stack);
    	// if the root value less then target, no need to go deeper since it is bst
    	if(root.val > target) return;
    	stack.push(root.val);
    	inorder1(root.right, target, stack);
    }

  • Combine those two parts together since just the differ just focus on traversal order

1
2
3
4
5
6
7
private void inorder(TreeNode root, double target, boolean reverse, Stack<Integer> stack){
        if(root == null) return;
        inorder(reverse ? root.right:root.left, target, reverse, stack);
        if((reverse && root.val<=target) || (!reverse && root.val > target)) return;
        stack.push(root.val);
        inorder(reverse ? root.left : root.right, target, reverse, stack);
    }
  • Final solution: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        List<Integer> res = new ArrayList<>();
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();
        
        inorder1(root, target, s1);
        inorder2(root,target, s2);
        // inorder(root, target, false, s1);
        // inorder(root, target, true, s2);
        
        while(k-- > 0){
            if(s1.isEmpty()) res.add(s2.pop());
            else if(s2.isEmpty()) res.add(s1.pop());
            else if(Math.abs(s1.peek() - target) < Math.abs(s2.peek() - target)) res.add(s1.pop());
            else res.add(s2.pop());
        }
        return res;
    }
    
    private void inorder(TreeNode root, double target, boolean reverse, Stack<Integer> stack){
        if(root == null) return;
        inorder(reverse ? root.right:root.left, target, reverse, stack);
        if((reverse && root.val<=target) || (!reverse && root.val > target)) return;
        stack.push(root.val);
        inorder(reverse ? root.left : root.right, target, reverse, stack);
    }
    
    private void inorder1(TreeNode root, double target, Stack<Integer> stack){
        if(root==null) return;
        inorder1(root.right, target, stack);
        if(root.val<=target) return;
        stack.push(root.val);
        inorder1(root.left, target, stack);
    }
    private void inorder2(TreeNode root, double target, Stack<Integer> stack){
        if(root==null) return;
        inorder2(root.left, target, stack);
        if(root.val>target) return;
        stack.push(root.val);
        inorder2(root.right, target, stack);
    }
}