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 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

[暴力解法]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

［思维问题］：

以为用直接用helper函数就可以：dfs(root.left, k - root.val) || dfs(root.right, k - root.val);

但是这样做的问题是一定会把当前的root.val包括进去，然而结果其实可以不包括当前root节点的值

［一句话思路］：

任意取点时，把之前出现过的点先用hashset缓存一下。头一次见。

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

任意取点时，把之前出现过的点先用hashset缓存一下。头一次见。

［复杂度］：Time complexity: O(n) Space complexity: O(n)

［英文数据结构或算法，为什么不用别的数据结构或算法］：

哈希集合缓存

［关键模板化代码］：

DFS，但是要缓存

if(root == null)return false;

        //exit: set contains k - root.val;

        if (set.contains(k - root.val)) return true;

        //store the root.val at present

        set.add(root.val);

        //expand to left, right

        return dfs(root.left, set, k) || dfs(root.right, set, k);

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

[代码风格] ：

/**

 * 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) {

        HashSet<Integer> set = new HashSet<>();

        return dfs(root, set, k);

    }

    public boolean dfs(TreeNode root, HashSet<Integer> set, int k){

        if(root == null)return false;

        //exit: set contains k - root.val;

        if (set.contains(k - root.val)) return true;

        //store the root.val at present

        set.add(root.val);

        //expand to left, right

        return dfs(root.left, set, k) || dfs(root.right, set, k);

    }

}

巴特西

653. Two Sum IV - Input is a BST 二叉树版本

最新文章

热门文章