LeetCode.653.Two Sum IV - Input is a BST 两数之和4-输入是BST

题目描述

653 Two Sum IV - Input is a BST
https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst/

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.

Example 1:

Input:
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

Output: True

Example 2:

Input:
    5
   / \
  3   6
 / \   \
2   4   7

Target = 28

Output: False

---

相似题目

LeetCode.001.Two Sum 两数之和
LeetCode.653.Two Sum IV - Input is a BST 两数之和4-输入是BST
LeetCode.532.K-diff Pairs in an Array 数组中的k-diff数对

LeetCode.016.3Sum Closest 最接近的三数之和
LeetCode.015.3Sum 三数之和

---

解题过程

two sum 问题的变种，输入是一个BST，没想到如何使用BST的性质，写了个适用所有二叉树的。
时间复杂度 O(n)，空间复杂度 O(n)
官方题解中，前两个方法也都没用BST的性质，最后一个解法，先把BST中序遍历为升序数组，然后使用左右双指针O(n)遍历，也是一种思路。
总的来说还是递归遍历加map更简单。

private static class SolutionV2020 {
    public boolean findTarget(TreeNode root, int k) {
        Map<Integer, Boolean> map = new HashMap<>();
        return preOrderTraverse(root, k, map);
    }

    private boolean preOrderTraverse(TreeNode root, int k, Map<Integer, Boolean> map) {
        if (null == root) {
            return false;
        }
        if (map.containsKey(k - root.val)) {
            return true;
        }
        map.put(root.val, false);
        return preOrderTraverse(root.left, k, map) || preOrderTraverse(root.right, k, map);
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_653_TwoSum4BST.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_653_TwoSum4BST.java

---