剑指 Offer II 056.二叉搜索树中两个节点之和

1、题干

给定一个二叉搜索树的 根节点 root 和一个整数 k , 请判断该二叉搜索树中是否存在两个节点它们的值之和等于 k 。假设二叉搜索树中节点的值均唯一。

 

示例 1：

输入: root = [8,6,10,5,7,9,11], k = 12
输出: true
解释: 节点 5 和节点 7 之和等于 12

示例 2：

输入: root = [8,6,10,5,7,9,11], k = 22
输出: false
解释: 不存在两个节点值之和为 22 的节点

 

提示：

• 二叉树的节点个数的范围是  [1, 104].
• -104 <= Node.val <= 104
• root 为二叉搜索树
• -105 <= k <= 105

 

注意：本题与主站 653 题相同： https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst/

2、解法1

DFS遍历+哈希查找：DFS遍历所有节点node，在哈希表set中查找是否存在k - node.val，若存在则返回true否则继续遍历直至结束则返回false。

3、代码

var findTarget = function (root, k) {
    const set = new Set();
    function dfs(node) {
        if (!node) return false;
        if (set.has(k - node.val)) return true;
        set.add(node.val);
        return dfs(node.left) || dfs(node.right);
    }
    return dfs(root);
};

4、复杂度

时间复杂度：$O(n)$

空间复杂度：$O(n)$

5、执行结果

6、解法2

DFS遍历+DFS二分查找：DFS遍历所有节点node，利用BST特性进行DFS二分查找是否存在k - node.val，若存在则返回true否则继续遍历直至结束则返回false。

这里二分搜索的时间复杂度受到二叉树平衡性的影响，最坏情况下二叉树可能退化成链表，导致搜索时间复杂度为$O(n)$，总体时间复杂度为$O(n^2)$

7、代码

var findTarget = function (root, k) {
    function find(node, num) {
        if (!node) return false;
        if (num === node.val) return true;
        return num > node.val ? find(node.right, num) : find(node.left, num);
    }

    function findSum(node, num) {
        if (!node) return false;
        return (num !== 2 * node.val && find(root, num - node.val)) || findSum(node.right, num) || findSum(node.left, num);
    }

    return findSum(root, k);
};

8、复杂度

时间复杂度：平衡二叉搜索树的情况下为$O(nlogn)$ ，非平衡二叉搜索树的情况下超过$O(nlogn)$，最差为$O(n^2)$

空间复杂度：$O(1)$

9、执行结果