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储存节点值，不用像我这样再次搜索整棵树
• 先序遍历，将节点值存入数组，这个数组是有序的，然后搜索这个数组