LeetCode 653. 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 :
Input: 
    
   / \
     
 / \   \
      

Target = 

Output: True
Example :
Input: 
    
   / \
     
 / \   \
      

Target = 

Output: False
           

又是一道easy題，感覺自己做法并不好

思路

對于書中的每一個節點v，檢視樹中是否存在target-v這個值。特别的，當target = 2 * v 時，不進行查找

代碼

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean findTarget(TreeNode root, int k) {
        return preOrder(root, k, root);
    }

    public boolean preOrder(TreeNode root, int v, TreeNode r) {
        if (root == null) return false;
        if (v !=  * (v - root.val) && find(r, v - root.val)) return true;
        else return preOrder(root.right, v, r) || preOrder(root.left, v, r);
    }

    public boolean find(TreeNode root, int v) {
        if (root == null) return false;
        if (root.val < v) return find(root.right, v);
        else if (root.val > v) return find(root.left, v);
        else return true;
    }
}
           

沒想到leetcode的思路也差不多，可能是我代碼寫醜了

leetcode

• 使用hashset儲存節點值，不用像我這樣再次搜尋整棵樹
• 先序周遊，将節點值存入數組，這個數組是有序的，然後搜尋這個數組