LeetCode653-两数之和IV-输入BST

题目链接

英文链接：https://leetcode.com/problems/two-sum-iv-input-is-a-bst/

中文链接：https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst/

题目详述

给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

案例 1:

输入: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

输出: True

案例 2:

输入: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 28

输出: False

题目详解

LeetCode1-两数之和 是普通数组的两数之和，LeetCode167-两数之和II-输入有序数组 是有序数组的两数之和，本题是二叉搜索树的两数之和。

方法一：

• 直接运用 HashSet 进行记录。
• 在遍历二叉搜索树的过程中进行判断，类似于 LeetCode1-两数之和。
• 时间复杂度为 O(n)。
• 空间复杂度为 O(n)。

public class LeetCode_00653 {

    // 运用 HashSet
    public boolean findTarget(TreeNode root, int k) {
        Set<Integer> set = new HashSet<>();
        return preOrder(root, k, set);
    }

    private boolean preOrder(TreeNode root, int k, Set<Integer> set) {
        if (root == null) {
            return false;
        }
        if (set.contains(k - root.val)) {
            return true;
        }
        set.add(root.val);
        return preOrder(root.left, k, set) || preOrder(root.right, k, set);
    }
}

方法二：

• 由于是一棵二叉搜索树，中序遍历可以得到一个有序序列。
• 问题就转化为了 LeetCode167-两数之和II-输入有序数组，运用双指针进行扫描即可。
• 时间复杂度为 O(n)。
• 空间复杂度为 O(n)。

public class LeetCode_00653 {

    // 中序遍历得到有序数组后运用双指针
    public boolean findTarget(TreeNode root, int k) {
        List<Integer> list = new ArrayList<>();
        inOrder(root, list);
        int i = 0, j = list.size() - 1;
        while (i < j) {
            int s = list.get(i) + list.get(j);
            if (s < k) {
                ++i;
            } else if (s > k) {
                --j;
            } else {
                return true;
            }
        }
        return false;
    }

    private void inOrder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        inOrder(root.left, list);
        list.add(root.val);
        inOrder(root.right, list);
    }
}

方法三：

• 对每一个结点进行二分查找。
• 从根节点开始，遍历每一个结点 cur，判断在这棵树中是否存在另一个结点满足两个结点的元素之和等于目标值。
  • 判断当前结点是否存在存在另一个满足条件的结点时也需要遍历整棵树。
  • 编写一个方法传入当前结点 cur，二叉树的根结点 root，目标值与当前结点元素之差（要搜索到的值，记为 val）。
  • 若结点的值小于 val，在结点的左子树中进行搜索。
  • 若结点的值大于 val，在结点的右子树中进行搜索。
  • 若结点的值等于 val，注意并不能直接返回 true，这个结点可能是我们正在判断的结点，也就是搜索到了它自己本身，返回条件为 cur != root。
• 若满足直接返回 true，不满足递归遍历当前结点的左子树和右子树。
• 在整个遍历过程中需要注意边界条件。
• 时间复杂度为 O(nh)，h 为二叉搜索树的高度，最好情况为 logn，最坏情况为 n。
• 空间复杂度为 O(h)。

public class LeetCode_00653 {

    // 对每一个结点进行二分查找
    public boolean findTarget(TreeNode root, int k) {
        return dfs(root, root, k);
    }

    private boolean dfs(TreeNode cur, TreeNode root, int k) {
        if (cur == null) {
            return false;
        }
        return search(cur, root, k - cur.val) || dfs(cur.left, root, k) || dfs(cur.right, root, k);
    }

    private boolean search(TreeNode cur, TreeNode root, int val) {
        if (root == null) {
            return false;
        }
        if (val < root.val) return search(cur, root.left, val);
        if (val > root.val) return search(cur, root.right, val);
        return cur != root;
    }
}