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

大家好，我是小庄，一个专心于互联网技术的深漂打工仔。

周末到了，又可以开始提升自我(卷)啦。

小庄将带动大家继续将Leetcode的算法题安排上～保持算法思维，靠近大厂多一点点。

一、题目链接

二、具体代码

补充：以下为小庄在Leetcode上提交的代码，非常欢迎大家在互联网技术交流群中发表更好的代码和题解，一起学习～关于如何加群，公zhong号【深漂程序员小庄】后台回复【加群】，即可加入互联网技术交流群一起监督学习。
话不多说，上代码：

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {boolean}
 */
/*
    1、方法：深度优先搜索 + 中序遍历 + 双指针
    2、复杂度分析：
    （1）时间复杂度：O(n)，其中 n 为二叉搜索树的大小。我们需要遍历整棵树一次，
        并对得到的升序数组使用双指针遍历。
    （2）空间复杂度：O(n)，其中 n 为二叉搜索树的大小。主要为升序数组的开销。
 */
var inorderTraversal = function(root, list) {
    if ( root === null ) {
        return;
    }
    inorderTraversal(root.left, list);
    list.push(root.val);
    inorderTraversal(root.right, list);
}
var findTarget = function(root, k) {
    let list = [];
    // 1、对二叉搜索书进行递归中序遍历，获得升序后的数组;
    inorderTraversal(root, list);
    // 2、双指针法，检验升序数组中是否存在两个数之和等于k
    let left = 0;
    let right = list.length - 1;
    /*
        注意题目条件: 
            二叉搜索树中的值均唯一，所以升序数组中不可能存在两个相同的数；
            所以如果当left指针和right指针指向相同，说明不存在两数之和
            等于k,因此退出循环。
     */
    while(left < right) {
        if(list[left] + list[right] === k) {
            return true;
        } else {
            if(list[left] + list[right] < k) {
                left++;
            }else {
                right--;
            }
        }
    }
    // 未找到，直接返回false
    return false;
};

三、具体思路

1、注意到二叉搜索树的中序遍历是升序排列的，我们可以将该二叉搜索树的中序遍历的结果记录下来，得到一个升序数组。

2、这样该问题即转化为「167. 两数之和 II - 输入有序数组」。我们可以使用双指针解决它。

3、具体地，我们使用两个指针分别指向数组的头尾，当两个指针指向的元素之和小于 k 时，让左指针右移；当两个指针指向的元素之和大于 k 时，让右指针左移；当两个指针指向的元素之和等于 k 时，返回 True。

4、最终，当左指针和右指针重合时，树上不存在两个和为 k 的节点，返回 False。

四、补充部分

关注公zhong号：【深漂程序员小庄】：内含丰富的学习资源和面试经验（不限前端、java、算法），还有学习交流群可加，并且还有各大厂大佬可一起交流学习，一起进步～添加小庄微信，回复【加群】，可加入互联网技术交流群。

最后编辑于：2022.05.29 20:33:51