Two Sum IV - Input is a BST

https://leetcode.com/problems/two-sum-iv-input-is-a-bst/description/

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Thoughts

这道题有多种解法。它和2sum的唯一区别就是它是树而后者input是数组。因此我们可以利用BST的性质做中序遍历生成一个排好序的数组再用2sum解。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private void inOrder(TreeNode node, List<Integer> list) {
        if (node == null) {
            return;
        }

        inOrder(node.left, list);
        list.add(node.val);
        inOrder(node.right, list);
    }

    public boolean findTarget(TreeNode root, int k) {
        List<Integer> list = new ArrayList<>();
        inOrder(root, list);
        for (int i = 0, j = list.size() - 1; i < j; ) {
            if (list.get(i) + list.get(j) == k) {
                return true;
            } else if (list.get(i) + list.get(j) < k) {
                i++;
            } else {
                j--;
            }
        }

        return false;
    }
}

Analysis

时间复杂度O(n), 空间复杂度O(n)

Ver.2

https://discuss.leetcode.com/topic/100000/java-simple-ac-with-time-o-n-space-o-log-n-in-average

看到个挺巧妙的解法, 用两个栈实现类似俩指针的效果, 左栈存当前最小的数们(左子树), 右栈存当前最大的数们(右子树). stackNext用于把"指针" (peek())移到下一个数.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean findTarget(TreeNode root, int k) {
        if (root == null) {
            return false;
        }

        Stack<TreeNode> lstack = new Stack<>(); 
        Stack<TreeNode> rstack = new Stack<>();
        stackAdd(lstack, root, true);
        stackAdd(rstack, root, false);
        while (lstack.peek() != rstack.peek()) {
            int val = lstack.peek().val + rstack.peek().val;
            if (val == k) {
                return true;
            } else if (val < k) {
                stackNext(lstack, true);
            } else {
                stackNext(rstack, false);
            }
        }
        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);
        }
    }
}