LeetCode-【樹】-653. 兩數之和 IV - 輸入 BST

給定一個二叉搜尋樹和一個目标結果，如果 BST 中存在兩個元素且它們的和等于給定的目标結果，則傳回 true。

案例 1:

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

Target = 9

輸出: True
      

案例 2:

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

Target = 28

輸出: False      

題解：可能大多數人覺得本題很簡單，嗯，我也這樣想過，但真正做的時候，問題頻出。

一般的思路：周遊樹的每一個節點，用目标值減去這個節點值獲得值x，然後再周遊一次二叉樹，看是否能找到值等于x且不是目前節點的節點，如果找到，直接傳回true，否則傳回false；思路好像很清晰，好吧，想想代碼實作，嗯。。，先是周遊二叉樹，就用遞歸分别周遊左右子樹好了，遞歸結束的條件，當然是找到符合要求的節點了，怎樣判斷節點符合要求，好像二叉樹有個性質（每個節點的右子節點的值一定大于該節點的值，左子節點的值一定小于該節點的值），那周遊的時候就可通過值大小判斷接下來應該周遊的節點是左還是右。好了，上代碼。。。

class Solution {
    static boolean f;
    public static boolean dfs(TreeNode root,int x){
        if(root==null)
            return false;
        if(root.val==x){
            return true;
        }
        if(root.val<x){
            return dfs(root.right,x);
        }
        if(root.val>x){
            return dfs(root.left,x);
        }
        return false;
    }
    public static void find(TreeNode root,TreeNode cur,int k){
        if(cur==null){
            return;
        }
        if(f){
            return;
        }
        if(cur.val!=k-cur.val)
            f=dfs(root,k-cur.val);
        find(root,cur.left,k);
        find(root,cur.right,k);
        //return false;
    }
    public boolean findTarget(TreeNode root, int k) {
        if(root==null)
            return false;
        f=false;
        find(root,root,k);
        return f;
    }
}
           

使用set的層次周遊解法，層次周遊知道吧，set特性知道吧，不做過多解釋了。。。

class Solution {
    public boolean findTarget(TreeNode root, int k) {
        ArrayDeque<TreeNode> q=new ArrayDeque<>();
        Set<Integer> set=new HashSet<>();
        q.offer(root);
        while(!q.isEmpty()){
            root=q.poll();
            if(set.contains(k-root.val))
                return true;
            set.add(root.val);
            if(root.right!=null)
                q.offer(root.right);
            if(root.left!=null)
                q.offer(root.left);
        }
        return false;
    }
}