力扣 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：
5
/ \
3 6
/ \ \
2 4 7输入: root = , k = 9
输出: true
示例 2：
5
/ \
3 6
/ \ \
2 4 7输入: root = , k = 28
输出: false
提示:
二叉树的节点个数的范围是.
-10^4右子树
递归实现：
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class BinaryTree {
public void preorderTraversal(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.val + " "); // 先访问根节点
preorderTraversal(root.left); // 遍历左子树
preorderTraversal(root.right); // 遍历右子树
}
}3. 后序遍历 (Postorder Traversal)
遍历次序： 左子树 -> 右子树 -> 根节点
递归实现：
public class BinaryTree {
public void inorderTraversal(TreeNode root) {
if (root == null) {
return;
}
inorderTraversal(root.left); // 遍历左子树
System.out.print(root.val + " "); // 访问根节点
inorderTraversal(root.right); // 遍历右子树
}
}总结
[*]前序遍历：先访问根节点，再遍历左子树和右子树。
[*]中序遍历：先遍历左子树，再访问根节点，末了遍历右子树。
[*]后序遍历：先遍历左子树，再遍历右子树，末了访问根节点。
这些遍历方式的递归实现思绪基本相同，区别在于访问根节点的时机不同。在现实应用中，可以根据需求选择不同的遍历方式。
前中后是以 root 的节点为主视角，看什么时候被访问。
v1-前序遍历
思绪
我们可以把整个数组完全构建出来，然后复用从前的解法。
固然这样会比较慢，我们可以在遍历的时候找到对应的结果。
传递的值更新问题，我们用 resFlag 数组来记录末了的结果。
实现
public class BinaryTree {
public void postorderTraversal(TreeNode root) {
if (root == null) {
return;
}
postorderTraversal(root.left); // 遍历左子树
postorderTraversal(root.right); // 遍历右子树
System.out.print(root.val + " "); // 访问根节点
}
}结果
3ms 79.82
v2-中序遍历
思绪
采用中序遍历，其他保持不变。
代码
class Solution {
public boolean findTarget(TreeNode root, int k) {
// 构建结果列表
Set<Integer> numSet = new HashSet<>();
int[] resFlag = new int[]{1};
resFlag = 0;
preOrderTravel(numSet, root, k, resFlag);
return resFlag != 0;
}
private void preOrderTravel(Set<Integer> numSet,
TreeNode root,
int k,
int[] resFlag) {
if(root == null || resFlag != 0) {
return;
}
// 符合
int value = root.val;
if(numSet.contains(k - value)) {
resFlag = 1;
return;
}
numSet.add(value);
preOrderTravel(numSet, root.left, k, resFlag);
preOrderTravel(numSet, root.right, k, resFlag);
}
}结果
public boolean findTarget(TreeNode root, int k) {
// 构建结果列表
Set<Integer> numSet = new HashSet<>();
int[] resFlag = new int[]{1};
resFlag = 0;
inOrderTravel(numSet, root, k, resFlag);
return resFlag != 0;
}
private void inOrderTravel(Set<Integer> numSet,
TreeNode root,
int k,
int[] resFlag) {
if(root == null || resFlag != 0) {
return;
}
inOrderTravel(numSet, root.left, k, resFlag);
// 符合
int value = root.val;
if(numSet.contains(k - value)) {
resFlag = 1;
return;
}
numSet.add(value);
inOrderTravel(numSet, root.right, k, resFlag);
}v3-后序遍历
思绪
很简朴，调整为后续遍历即可。
实现
3ms 79.82%结果
4ms 29.82%
估计是服务器颠簸，也和测试用例有一定的关系。
v4-层序遍历
层序遍历
层序遍历（Level Order Traversal）是按层级次序从上到下、从左到右遍历二叉树。
与前序、中序、后序不同，层序遍历通常是使用广度优先搜索（BFS）实现的，常见的做法是使用队列来辅助遍历。
层序遍历的实现步骤：
[*]使用一个队列存储当前层的节点。
[*]先将根节点到场队列。
[*]然后逐层遍历队列，取出队首节点，访问该节点，并将它的左右子节点（如果有的话）依次到场队列。
[*]重复这个过程，直到队列为空。
层序遍历的 Java 实现：
public boolean findTarget(TreeNode root, int k) {
// 构建结果列表
Set<Integer> numSet = new HashSet<>();
int[] resFlag = new int[]{1};
resFlag = 0;
postOrderTravel(numSet, root, k, resFlag);
return resFlag != 0;
}
private void postOrderTravel(Set<Integer> numSet,
TreeNode root,
int k,
int[] resFlag) {
if(root == null || resFlag != 0) {
return;
}
postOrderTravel(numSet, root.left, k, resFlag);
postOrderTravel(numSet, root.right, k, resFlag);
// 符合
int value = root.val;
if(numSet.contains(k - value)) {
resFlag = 1;
return;
}
numSet.add(value);
}代码说明：
[*]队列：我们使用 LinkedList 来实现队列，因为队列的特点是先入先出（FIFO）。
[*]访问节点：每次从队列中取出一个节点，访问它并将其左右子节点到场队列。
[*]层级遍历：这种方式会保证节点按照层次次序被访问，父节点先于子节点。
结合本题
// 层序遍历
public void levelOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root); // 将根节点加入队列
while (!queue.isEmpty()) {
TreeNode node = queue.poll(); // 取出队首元素
System.out.print(node.val + " "); // 访问当前节点
if (node.left != null) {
queue.offer(node.left); // 左子节点加入队列
}
if (node.right != null) {
queue.offer(node.right); // 右子节点加入队列
}
}
}结果
4ms 29.82
小结
层序遍历放在本题看起来没有特别大的优势。
不过层序遍历在有些场景照旧很有用的，比如 T337 打家劫舍 III。
v5-另有高手
思绪
除了这 4 种方式，另有其他更快的方式吗？
那就是我们其实对二叉树的理解照旧不够深入。
中序遍历之后，结果其实是一个升序数组。
也就是我们可以利用排序后的数组举行处理，结合 T167.
中序是：left>val>right
回顾 T167
其实就是两步
1）构建有序数组
2）双指针直接获取
固然双指针也可以用二分法，此处不再赘述、
java
public boolean findTarget(TreeNode root, int k) {
// 构建结果列表
Set<Integer> numSet = new HashSet<>();
// 队列 模拟
int[] resFlag = new int[]{1};
resFlag = 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
levelOrderTravel(numSet, queue, k, resFlag);
return resFlag != 0;
}
private void levelOrderTravel(Set<Integer> numSet,
Queue<TreeNode> queue,
int k,
int[] resFlag) {
while (!queue.isEmpty()) {
// 取出
TreeNode root = queue.poll();
// 符合
int value = root.val;
if(numSet.contains(k - value)) {
resFlag = 1;
return;
}
numSet.add(value);
// 加入左右
if(root.left != null) {
queue.offer(root.left);
}
if(root.right != null) {
queue.offer(root.right);
}
}
}结果
public boolean findTarget(TreeNode root, int k) {
// 构建结果列表
Set<Integer> numSet = new HashSet<>();
int[] resFlag = new int[]{1};
resFlag = 0;
inOrderTravel(numSet, root, k, resFlag);
return resFlag != 0;
}
private void inOrderTravel(Set<Integer> numSet,
TreeNode root,
int k,
int[] resFlag) {
if(root == null || resFlag != 0) {
return;
}
inOrderTravel(numSet, root.left, k, resFlag);
// 符合
int value = root.val;
if(numSet.contains(k - value)) {
resFlag = 1;
return;
}
numSet.add(value);
inOrderTravel(numSet, root.right, k, resFlag);
}
小结
这种解法，其实已经很巧妙了。
本题的难度定位在简朴有点浪费，用到这种方式现实上已经结合了多个知识点。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]