[数据结构与算法]653. 两数之和 IV - 输入 BST（ 树的深度遍历 + 哈希表 ）

LeetCode：653. 两数之和 IV - 输入 BST

创建一个 ISet 集合用于保存已经遍历过的数据.

深度遍历树，当遍历到一个数后，用目标数字减去当前节点数字，在集合中是否存在

1.如果存在则找到答案，返回true

2.如果没有找到就将当前的数字加入到集合中。继续遍历下一个节点。

AC Code

public class Solution {
    ISet<int> set = new HashSet<int>();
    public bool FindTarget(TreeNode root, int k) {
        if (root == null) { 
            return false;
        }

        if (set.Contains(k - root.val)) { 
            return true;
        }

        set.Add(root.val);

        return (FindTarget(root.left, k) || FindTarget(root.right, k));
    }
}





/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */