Java Simple AC with Time O(n) Space O(log n) in Average


  • 16
    L

    There are few possible solutions:

    (1) Use hash set to keep those visited value for fast lookup.

    -- It can be applied to any kinds of tree. Time/Space: n/n

    (2) Dump values to array list in-order and search by the way just like in 2sum.

    -- Time/Space: n/n

    (3) Use the stack and search just like 2sum without dumping all the value out in the beginning.

    -- Time/Space: n/logn in average

    If I have to choose one from them, I would prefer the third one because it takes advantage of the property of BST and is with lower space complexity in average. Its code is shown below.

        public boolean findTarget(TreeNode root, int k) {
            if(root == null) return false;
        	Stack<TreeNode> l_stack = new Stack<>();
        	Stack<TreeNode> r_stack = new Stack<>();
        	stackAdd(l_stack, root, true);
        	stackAdd(r_stack, root, false);
        	while(l_stack.peek() != r_stack.peek()){
        	    int n = l_stack.peek().val + r_stack.peek().val;
        	    if(n == k){
        		return true;
        	    }else if(n > k){
        		stackNext(r_stack, false);
        	    }else{
    		stackNext(l_stack, true);
        	    }
        	}
        	return false;
        }
        
        private void stackAdd(Stack<TreeNode> stack, TreeNode node, boolean isLeft){
        	while(node != null){
        	    stack.push(node);
                node = (isLeft) ? node.left : node.right;
        	}
        }
    
        private void stackNext(Stack<TreeNode> stack, boolean isLeft){
        	TreeNode node = stack.pop();
        	if(isLeft){
        	    stackAdd(stack, node.right, isLeft);
        	}else{
        	    stackAdd(stack, node.left, isLeft);
        	}
        }
    

  • 0
    Y

    Very concise solution!


  • 1

    Brilliant solution, here is the python version

      def __add_left_nodes (self, stack, node):
        while node:
          stack.append(node)
          node = node.left
    
      def __add_right_nodes (self, stack, node):
        while node:
          stack.append(node)
          node = node.right
    
      # O(n) time, O(logn) space
      def findTarget(self, root, k):
        if root is None:
          return False
    
        l, r = [], []
        self.__add_left_nodes (l, root)
        self.__add_right_nodes(r, root)
    
        # the root is pusted to the bottom of the stack
        while l[-1] is not r[-1]:
          n = l[-1].val + r[-1].val
          if n == k:
            return True
          elif n > k:
            node = r.pop()
            # Add children smaller than node but larger than node.left
            if node.left:
              self.__add_right_nodes (r, node.left)
          else:
            node = l.pop()
            # Add children larger than node but smaller than node.right
            if node.right:
              self.__add_left_nodes(l, node.right)     
    
        return False
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.