力扣 653. 两数之和 IV 二叉树/binary-tree two-sum IV

数组系列

力扣数据结构之数组-00-概览
力扣.53 最大子数组和 maximum-subarray
力扣.128 最长连续序列 longest-consecutive-sequence
力扣.1 两数之和 N 种解法 two-sum
力扣.167 两数之和 II two-sum-ii
力扣.170 两数之和 III two-sum-iii
力扣.653 两数之和 IV two-sum-IV
力扣.015 三数之和 three-sum
力扣.016 最靠近的三数之和 three-sum-closest
力扣.259 较小的三数之和 three-sum-smaller
标题

给定一个二叉搜索树 root 和一个目的结果 k，如果二叉搜索树中存在两个元素且它们的和等于给定的目的结果，则返回 true。
示例 1：

1.         5
2.        / \
3.       3   6
4.      / \    \
5.     2   4    7

复制代码

输入: root = [5,3,6,2,4,null,7], k = 9
输出: true
示例 2：

1.         5
2.        / \
3.       3   6
4.      / \    \
5.     2   4    7

复制代码

输入: root = [5,3,6,2,4,null,7], k = 28
输出: false
提示:
二叉树的节点个数的范围是  [1, 10^4].
-10^4  右子树
递归实现：

1. class TreeNode {
2.     int val;
3.     TreeNode left;
4.     TreeNode right;
5.     TreeNode(int x) {
6.         val = x;
7.     }
8. }
10. public class BinaryTree {
11.     public void preorderTraversal(TreeNode root) {
12.         if (root == null) {
13.             return;
14.         }
15.         System.out.print(root.val + " "); // 先访问根节点
16.         preorderTraversal(root.left);    // 遍历左子树
17.         preorderTraversal(root.right);   // 遍历右子树
18.     }
19. }

复制代码

3. 后序遍历 (Postorder Traversal)

遍历次序： 左子树 -> 右子树 -> 根节点
递归实现：

1. public class BinaryTree {
2.     public void inorderTraversal(TreeNode root) {
3.         if (root == null) {
4.             return;
5.         }
6.         inorderTraversal(root.left);     // 遍历左子树
7.         System.out.print(root.val + " "); // 访问根节点
8.         inorderTraversal(root.right);    // 遍历右子树
9.     }
10. }

复制代码

总结

• 前序遍历：先访问根节点，再遍历左子树和右子树。
  
• 中序遍历：先遍历左子树，再访问根节点，末了遍历右子树。
  
• 后序遍历：先遍历左子树，再遍历右子树，末了访问根节点。
  

这些遍历方式的递归实现思绪基本相同，区别在于访问根节点的时机不同。在现实应用中，可以根据需求选择不同的遍历方式。
前中后是以 root 的节点为主视角，看什么时候被访问。
v1-前序遍历

思绪

我们可以把整个数组完全构建出来，然后复用从前的解法。
固然这样会比较慢，我们可以在遍历的时候找到对应的结果。
传递的值更新问题，我们用 resFlag 数组来记录末了的结果。
实现

1. public class BinaryTree {
2.     public void postorderTraversal(TreeNode root) {
3.         if (root == null) {
4.             return;
5.         }
6.         postorderTraversal(root.left);    // 遍历左子树
7.         postorderTraversal(root.right);   // 遍历右子树
8.         System.out.print(root.val + " "); // 访问根节点
9.     }
10. }

复制代码

结果

3ms 79.82
v2-中序遍历

思绪

采用中序遍历，其他保持不变。
代码

1. class Solution {
2.    public boolean findTarget(TreeNode root, int k) {
3.         // 构建结果列表
4.         Set<Integer> numSet = new HashSet<>();
6.         int[] resFlag = new int[]{1};
7.         resFlag[0] = 0;
8.         preOrderTravel(numSet, root, k, resFlag);
10.         return resFlag[0] != 0;
11.     }
13.     private void preOrderTravel(Set<Integer> numSet,
14.                                 TreeNode root,
15.                                 int k,
16.                                 int[] resFlag) {
17.         if(root == null || resFlag[0] != 0) {
18.             return;
19.         }
21.         // 符合
22.         int value = root.val;
23.         if(numSet.contains(k - value)) {
24.             resFlag[0] = 1;
25.             return;
26.         }
27.         numSet.add(value);
29.         preOrderTravel(numSet, root.left, k, resFlag);
30.         preOrderTravel(numSet, root.right, k, resFlag);
31.     }
32. }

复制代码

结果

1. public boolean findTarget(TreeNode root, int k) {
2.     // 构建结果列表
3.     Set<Integer> numSet = new HashSet<>();
4.     int[] resFlag = new int[]{1};
5.     resFlag[0] = 0;
6.     inOrderTravel(numSet, root, k, resFlag);
7.     return resFlag[0] != 0;
8. }
10. private void inOrderTravel(Set<Integer> numSet,
11.                            TreeNode root,
12.                            int k,
13.                            int[] resFlag) {
14.     if(root == null || resFlag[0] != 0) {
15.         return;
16.     }
17.     inOrderTravel(numSet, root.left, k, resFlag);
18.     // 符合
19.     int value = root.val;
20.     if(numSet.contains(k - value)) {
21.         resFlag[0] = 1;
22.         return;
23.     }
24.     numSet.add(value);
25.     inOrderTravel(numSet, root.right, k, resFlag);
26. }

复制代码

v3-后序遍历

思绪

很简朴，调整为后续遍历即可。
实现

1. 3ms 79.82%

复制代码

结果

4ms 29.82%
估计是服务器颠簸，也和测试用例有一定的关系。
v4-层序遍历

层序遍历

层序遍历（Level Order Traversal）是按层级次序从上到下、从左到右遍历二叉树。
与前序、中序、后序不同，层序遍历通常是使用广度优先搜索（BFS）实现的，常见的做法是使用队列来辅助遍历。
层序遍历的实现步骤：

• 使用一个队列存储当前层的节点。
  
• 先将根节点到场队列。
  
• 然后逐层遍历队列，取出队首节点，访问该节点，并将它的左右子节点（如果有的话）依次到场队列。
  
• 重复这个过程，直到队列为空。
  

层序遍历的 Java 实现：

1.     public boolean findTarget(TreeNode root, int k) {
2.         // 构建结果列表
3.         Set<Integer> numSet = new HashSet<>();
5.         int[] resFlag = new int[]{1};
6.         resFlag[0] = 0;
7.         postOrderTravel(numSet, root, k, resFlag);
9.         return resFlag[0] != 0;
10.     }
12.     private void postOrderTravel(Set<Integer> numSet,
13.                                  TreeNode root,
14.                                  int k,
15.                                  int[] resFlag) {
16.         if(root == null || resFlag[0] != 0) {
17.             return;
18.         }
20.         postOrderTravel(numSet, root.left, k, resFlag);
22.         postOrderTravel(numSet, root.right, k, resFlag);
24.         // 符合
25.         int value = root.val;
26.         if(numSet.contains(k - value)) {
27.             resFlag[0] = 1;
28.             return;
29.         }
30.         numSet.add(value);
31.     }

复制代码

代码说明：

• 队列：我们使用 LinkedList 来实现队列，因为队列的特点是先入先出（FIFO）。
  
• 访问节点：每次从队列中取出一个节点，访问它并将其左右子节点到场队列。
  
• 层级遍历：这种方式会保证节点按照层次次序被访问，父节点先于子节点。
  

结合本题

1. // 层序遍历
2. public void levelOrderTraversal(TreeNode root) {
3.     if (root == null) {
4.         return;
5.     }
6.    
7.     Queue<TreeNode> queue = new LinkedList<>();
8.     queue.offer(root); // 将根节点加入队列
9.    
10.     while (!queue.isEmpty()) {
11.         TreeNode node = queue.poll(); // 取出队首元素
12.         System.out.print(node.val + " "); // 访问当前节点
13.         
14.         if (node.left != null) {
15.             queue.offer(node.left); // 左子节点加入队列
16.         }
17.         if (node.right != null) {
18.             queue.offer(node.right); // 右子节点加入队列
19.         }
20.     }
21. }

复制代码

结果

4ms 29.82
小结

层序遍历放在本题看起来没有特别大的优势。
不过层序遍历在有些场景照旧很有用的，比如 T337 打家劫舍 III。
v5-另有高手

思绪

除了这 4 种方式，另有其他更快的方式吗？
那就是我们其实对二叉树的理解照旧不够深入。
中序遍历之后，结果其实是一个升序数组。
也就是我们可以利用排序后的数组举行处理，结合 T167.
中序是：left>val>right
回顾 T167

其实就是两步
1）构建有序数组
2）双指针直接获取
固然双指针也可以用二分法，此处不再赘述、
java

1.     public boolean findTarget(TreeNode root, int k) {
2.         // 构建结果列表
3.         Set<Integer> numSet = new HashSet<>();
5.         // 队列 模拟
6.         int[] resFlag = new int[]{1};
7.         resFlag[0] = 0;
9.         Queue<TreeNode> queue = new LinkedList<>();
10.         queue.offer(root);
11.         levelOrderTravel(numSet, queue, k, resFlag);
13.         return resFlag[0] != 0;
14.     }
16.     private void levelOrderTravel(Set<Integer> numSet,
17.                                   Queue<TreeNode> queue,
18.                                   int k,
19.                                   int[] resFlag) {
20.         while (!queue.isEmpty()) {
21.             // 取出
22.             TreeNode root = queue.poll();
23.             // 符合
24.             int value = root.val;
25.             if(numSet.contains(k - value)) {
26.                 resFlag[0] = 1;
27.                 return;
28.             }
29.             numSet.add(value);
31.             // 加入左右
32.             if(root.left != null) {
33.                 queue.offer(root.left);
34.             }
35.             if(root.right != null) {
36.                 queue.offer(root.right);
37.             }
38.         }
39.     }

复制代码

结果

public boolean findTarget(TreeNode root, int k) {
    // 构建结果列表
    Set<Integer> numSet = new HashSet<>();
    int[] resFlag = new int[]{1};
    resFlag[0] = 0;
    inOrderTravel(numSet, root, k, resFlag);
    return resFlag[0] != 0;
}

private void inOrderTravel(Set<Integer> numSet,
                           TreeNode root,
                           int k,
                           int[] resFlag) {
    if(root == null || resFlag[0] != 0) {
        return;
    }
    inOrderTravel(numSet, root.left, k, resFlag);
    // 符合
    int value = root.val;
    if(numSet.contains(k - value)) {
        resFlag[0] = 1;
        return;
    }
    numSet.add(value);
    inOrderTravel(numSet, root.right, k, resFlag);
}
小结

这种解法，其实已经很巧妙了。
本题的难度定位在简朴有点浪费，用到这种方式现实上已经结合了多个知识点。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。