代码随想录day15 | leetcode 110.平衡二叉树 257. 二叉树的所有路径 404.左叶子之和 222.完全二叉树的节点个数
110.平衡二叉树
概念：
- 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
- 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。
但leetcode中强调的深度和高度很明显是按照节点来计算的，如图：
关于根节点的深度究竟是1 还是 0，不同的地方有不一样的标准，leetcode的题目中都是以节点为一度，即根节点深度是1。但维基百科上定义用边为一度，即根节点的深度是0，我们暂时以leetcode为准（毕竟要在这上面刷题）。
因为求深度可以从上到下去查 所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）
class Solution {
public boolean isBalanced(TreeNode root) {
return getHeight(root) != -1;
}
private int getHeight(TreeNode node) {
if(node == null) return 0;
int leftHeight = getHeight(node.left);
if(leftHeight == -1) return -1;
int rightHeight = getHeight(node.right);
if(rightHeight == -1) return -1;
if(Math.abs(leftHeight - rightHeight) >1) {
return -1;
}
return 1 + Math.max(leftHeight,rightHeight);
}
}
return getHeight(root) != -1; 是用来判断给定的二叉树是否是平衡二叉树。
具体逻辑如下：
getHeight(root)的作用：
getHeight方法在递归计算树的高度时，同时会检测树是否是平衡二叉树：- 如果任意子树不平衡（左右子树高度差大于 1），则返回
-1，表示该子树不平衡。 - 如果树平衡，则返回实际的高度。
- 如果任意子树不平衡（左右子树高度差大于 1），则返回
- 为什么用
!= -1：- 如果
getHeight(root)返回-1，说明树中某些部分不满足平衡二叉树的定义（左右子树高度差不超过 1）。 - 如果
getHeight(root)返回的不是-1，说明整棵树是平衡的。
- 如果
- 最终的返回值：
- 如果
getHeight(root) != -1为true，表示整棵树是平衡二叉树。 - 如果
getHeight(root) != -1为false，表示整棵树不是平衡二叉树。
- 如果
总结：return getHeight(root) != -1; 是 isBalanced 方法的核心逻辑，判断树是否平衡。
leftHeight == -1 表示在递归过程中已经判断出当前的子树不是平衡二叉树。
具体来说：
- 在递归调用
getHeight(TreeNode root)的过程中，getHeight方法不仅仅计算树的高度，还会判断当前树是否平衡。 - 如果某一子树不平衡（左右子树高度差大于 1），
getHeight就返回-1，这是一个特殊值，用来标记当前树不平衡。 - 如果在处理左子树时，发现
getHeight(root.left)返回-1，说明左子树已经不平衡，此时直接返回-1，不再继续计算右子树的高度，优化了递归的性能。
因此：
leftHeight == -1表示左子树已经被判定为不平衡，后续逻辑可以直接终止进一步的判断。
这种方式通过早退出来避免不必要的计算，提高了算法效率。
257.二叉树的所有路径
这道题目要求从根节点到叶子的路径，所以用前序遍历
不显式用回溯写法
class Solution {
List<String> result = new ArrayList<>();
public List<String> binaryTreePaths(TreeNode root) {
deal(root, "");
return result;
}
public void deal(TreeNode node, String s) {
if (node == null)
return;
if (node.left == null && node.right == null) { //叶子节点处理
result.add(new StringBuilder(s).append(node.val).toString());
return;
}
String tmp = new StringBuilder(s).append(node.val).append("->").toString(); //中
deal(node.left, tmp); //左
deal(node.right, tmp); //右
}
}
在这段代码中，没有显式地使用“回溯”，是因为路径的状态管理是通过字符串的不可变性（StringBuilder.toString() 的新对象创建）隐式完成的，而不是通过修改和恢复状态的方式实现的。
回溯的定义
回溯是一种通过递归搜索所有可能的解，并在尝试一个解之后撤销之前的选择以继续搜索其他解的算法思想。通常回溯需要显式地修改状态（如列表或路径）并在递归返回后恢复状态。
代码为什么不需要显式回溯？
在这段代码中：
- 路径的状态是不可变的：
- 路径是用
StringBuilder拼接成新的字符串，并传递给递归函数的。 - 每次递归时，新的路径字符串
tmp是独立的，不会影响上层递归的路径。 - 由于路径状态不会被修改，也就不需要在递归返回时手动恢复状态。
- 路径是用
- 回溯通常用于可变对象：
- 回溯一般需要在递归前后对共享的可变数据结构（如列表）进行修改和恢复，例如添加或移除节点值。
- 本代码中使用了字符串（不可变对象）来保存路径，所以避免了对路径的显式管理，递归返回后原路径自然不受影响。
显式回溯写法
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();// 存最终的结果
if (root == null) {
return res;
}
List<Integer> paths = new ArrayList<>();// 作为结果中的路径
traversal(root, paths, res);
return res;
}
private void traversal(TreeNode root, List<Integer> paths, List<String> res) {
paths.add(root.val);// 前序遍历，中
// 遇到叶子结点
if (root.left == null && root.right == null) {
// 输出
StringBuilder sb = new StringBuilder();// StringBuilder用来拼接字符串，速度更快
for (int i = 0; i < paths.size() - 1; i++) {
sb.append(paths.get(i)).append("->");
}
sb.append(paths.get(paths.size() - 1));// 记录最后一个节点
res.add(sb.toString());// 收集一个路径
return;
}
// 递归和回溯是同时进行，所以要放在同一个花括号里
if (root.left != null) { // 左
traversal(root.left, paths, res);
paths.remove(paths.size() - 1);// 回溯
}
if (root.right != null) { // 右
traversal(root.right, paths, res);
paths.remove(paths.size() - 1);// 回溯
}
}
}
为什么需要 paths
- 记录路径上的节点值：
- 在递归过程中，
paths充当临时容器，存储从根节点到当前节点的路径。 - 每次递归调用都会在
paths中加入当前节点的值。 - 当遍历到叶子节点时，可以使用
paths构建完整的路径字符串。
- 在递归过程中，
- 实现路径的回溯：
- 递归过程中，每次向下遍历子树时都会修改
paths，因此需要在递归结束后将其恢复到之前的状态。 - 通过
paths.remove(paths.size() - 1)实现回溯，保证paths的内容始终只包含当前路径上的节点。 paths是一个共享的状态变量，递归进入时添加节点值，递归返回时移除节点值，这就是显式的回溯。
- 递归过程中，每次向下遍历子树时都会修改
两种方法的对比
| 特性 | 当前代码（无显式回溯） | 使用回溯的代码 |
|---|---|---|
| 路径存储方式 | 字符串，不可变 | 列表，可变 |
| 路径状态的管理 | 通过创建新字符串隐式完成 | 需要显式添加和移除节点 |
| 代码复杂度 | 更简单，无需恢复状态 | 较复杂，需要管理状态恢复 |
| 适用场景 | 当路径拼接操作简单且无需回溯时适用 | 当需要修改和恢复路径状态时适用 |
总结
本代码的实现依赖于字符串的不可变性，因此在递归中可以避免使用显式回溯来恢复路径状态。如果需要更复杂的路径状态管理（如使用列表存储路径），则必须使用回溯的思想。
回溯和递归是一一对应的，有一个递归，就要有一个回溯 回溯要和递归永远在一起，世界上最遥远的距离是你在花括号里，而我在花括号外！
404.左叶子之和
递归的遍历顺序为后序遍历（左右中），是因为要通过递归函数的返回值来累加求取左叶子数值之和。
判断当前节点是不是左叶子是无法判断的，必须要通过节点的父节点来判断其左孩子是不是左叶子。
如果该节点的左节点不为空，该节点的左节点的左节点为空，该节点的左节点的右节点为空，则找到了一个左叶子。（左的处理）
平时我们解二叉树的题目时，已经习惯了通过节点的左右孩子判断本节点的属性，而本题我们要通过节点的父节点判断本节点的属性。
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if(root == null) return 0;
if(root.left == null && root.right == null) return 0;
int leftNumber = sumOfLeftLeaves(root.left);
if(root.left != null && root.left.left == null && root.left.right == null){
leftNumber = root.left.val;
} //左
int rightNumber = sumOfLeftLeaves(root.right); //右
int sum = leftNumber + rightNumber; //中
return sum;
}
}
1. 递归计算左子树的左叶子节点的值
int leftNumber = sumOfLeftLeaves(root.left);
if(root.left != null && root.left.left == null && root.left.right == null) {
leftNumber = root.left.val;
}
- 首先递归处理左子树，计算左子树中左叶子节点的和。
- 然后检查当前节点的左子节点：- 条件
root.left != null && root.left.left == null && root.left.right == null判断左子节点是否是左叶子节点。- 如果是，将左子节点的值赋给
leftNumber，覆盖掉之前递归得到的值。
- 如果是，将左子节点的值赋给
2. 递归计算右子树的左叶子节点的值
int rightNumber = sumOfLeftLeaves(root.right);
- 递归处理右子树，计算右子树中左叶子节点的和。
- 不需要额外判断右子节点是否是叶子节点，因为右叶子节点不会被计入结果。
执行过程示例
假设二叉树如下：
3
/ \
9 20
/ \
15 7
路径跟踪：
- 根节点
3：- 左子树递归：
sumOfLeftLeaves(9) - 右子树递归：
sumOfLeftLeaves(20)
- 左子树递归：
- 节点
9：- 左子树递归：
sumOfLeftLeaves(null)-> 返回0 - 右子树递归：
sumOfLeftLeaves(null)-> 返回0 - 判断：节点
9是左叶子节点，返回值为9。
- 左子树递归：
- 节点
20：- 左子树递归：
sumOfLeftLeaves(15) - 右子树递归：
sumOfLeftLeaves(7)
- 左子树递归：
- 节点
15：- 左子树递归：
sumOfLeftLeaves(null)-> 返回0 - 右子树递归：
sumOfLeftLeaves(null)-> 返回0 - 判断：节点
15是左叶子节点，返回值为15。
- 左子树递归：
- 节点
7：- 左子树递归：
sumOfLeftLeaves(null)-> 返回0 - 右子树递归：
sumOfLeftLeaves(null)-> 返回0 - 判断：节点
7不是左叶子节点，返回值为0。
- 左子树递归：
总和计算：
- 节点
20：15 + 0 = 15 - 根节点
3：9 + 15 = 24
最终返回结果为：24。
222.完全二叉树的节点个数
普通二叉树写法
class Solution {
public int countNodes(TreeNode root) {
if(root == null) return 0;
int leftNumber = countNodes(root.left);
int rightNumber = countNodes(root.right);
int sum = 1 + leftNumber + rightNumber;
return sum;
}
}
左遍历，右遍历，中加上自己
完全二叉树写法
完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。
对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。
对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。
完全二叉树（一）如图：
完全二叉树（二）如图：
可以看出如果整个树不是满二叉树，就递归其左右孩子，直到遇到满二叉树为止，用公式计算这个子树（满二叉树）的节点数量。
这里关键在于如何去判断一个左子树或者右子树是不是满二叉树呢？
在完全二叉树中，如果递归向左遍历的深度等于递归向右遍历的深度，那说明就是满二叉树。如图：
在完全二叉树中，如果递归向左遍历的深度不等于递归向右遍历的深度，则说明不是满二叉树，如图：
class Solution {
public int countNodes(TreeNode root) {
if(root == null) return 0;
TreeNode left = root.left;
TreeNode right = root.right;
int leftDepth = 0, rightDepth = 0;
while(left != null) { //左深度
left = left.left;
leftDepth++;
}
while(right != null) { //右深度
right = right.right;
rightDepth++;
}
if(leftDepth == rightDepth) {
return (2 << leftDepth) - 1;
}
int lN = countNodes(root.left);
int rN = countNodes(root.right);
int sum = 1 + lN + rN;
return sum;
}
}
主要区别
| 特点 | 第一段代码 | 第二段代码 |
|---|---|---|
| 适用场景 | 针对完全二叉树，利用满二叉树的特性优化计算。 | 适用于任何二叉树。 |
| 时间复杂度 | 平均 O(log2N)O(\log^2 N)O(log2N)，最坏 O(N)O(N)O(N)。 | 最坏情况 O(N)O(N)O(N)。 |
| 优化逻辑 | 利用满二叉树的公式直接计算，减少递归次数。 | 每次递归都遍历左右子树，无优化。 |
| 实现复杂度 | 更复杂，需要计算左右子树深度并判断是否满二叉树。 | 更简单，直接递归遍历所有节点。 |
原文地址：https://blog.csdn.net/2302_81139517/article/details/144402948
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！