LeetCode 653. Two Sum IV - Input is a BST（两个数的和 IV - 输入是二叉搜索树）

题目描述

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

解法一

思路

如果单纯地把BST想象成是一个无序数组，那这题该怎么做呢？注意到题目并不要求返回具体哪两个数可以组成target，所以只需要维护一个set，用来保存期望的元素值；在遍历到每个元素的时候，首先检查set中有没有值与当前元素值相等，有则返回True，否则把target与当前元素值的差（期望元素值）放到set中；如果中途没有返回，则最后返回False，表示没有匹配的元素。

如上所述是对于无序数组的处理，那回到BST呢？只需要遍历BST就好了，遍历BST实际上就相当于是在遍历无序数组。

Python

class Solution:
    def findTarget(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: bool
        """
        candidates = set()
        stack = []
        while stack or root:
            if root:
                val = root.val
                if val in candidates:
                    return True
                else:
                    candidates.add(k - val)
                stack.append(root)
                root = root.left
            else:
                node = stack.pop()
                root = node.right
        return False

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean findTarget(TreeNode root, int k) {
        Set<Integer> candidates = new HashSet<>();
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.empty() || root != null) {
            if (root != null) {
                int val = root.val;
                if (candidates.contains(val)) {
                    return true;
                } else {
                    candidates.add(k - val);
                }
                stack.add(root);
                root = root.left;
            } else {
                TreeNode node = stack.pop();
                root = node.right;
            }
        }
        return false;
    }
}

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool findTarget(TreeNode *root, int k) {
        unordered_set<int> candidates;
        stack<TreeNode *> sta;
        while (!sta.empty() || root != nullptr) {
            if (root != nullptr) {
                int val = root->val;
                if (candidates.find(val) != candidates.end()) {
                    return true;
                } else {
                    candidates.insert(k - val);
                }
                sta.push(root);
                root = root->left;
            } else {
                TreeNode *node = sta.top();
                sta.pop();
                root = node->right;
            }
        }
        return false;
    }
};