代码随想录算法训练营第 15 天（树3）| 110.平衡二叉树、257. 二叉树的所有路径、404.左叶子之和、222.完全二叉树的节点个数
一、#110.平衡二叉树
关键思路：求高度（后序）
递归，从最下面的节点，依次判断其左右子树的高度，大于1就返回-1，小于1就返回当前值中大的加1就是此节点的高度。
class Solution {
public boolean isBalanced(TreeNode root) {
return getHeight(root) == -1 ? false:true;
}
private int getHeight(TreeNode node){
if(node == null) return 0;
int left = getHeight(node.left);
if(left == -1) return -1;
int right = getHeight(node.right);
if(right == -1) return -1;
return Math.abs(left - right)>1 ? -1 : 1 + Math.max(left, right);
}
}
二、#257. 二叉树的所有路径
关键思路：前序遍历
因为只有前序遍历，我们才能够让父节点去指向孩子节点
1、递归函数参数以及返回值：TreeNode，以及用来保存的数组，以便下次递归使用
2、终止条件是：这个节点左右孩子都为空
3、单层处理逻辑
注意中的顺序
class Solution {
List<String> result = new ArrayList<>();
public List<String> binaryTreePaths(TreeNode root) {
path(root, "");
return result;
}
private void path(TreeNode node, String s){
if(node == null) return;
//叶子节点
if(node.left==null && node.right==null){
//直接加上叶子节点的值
result.add(new StringBuilder(s).append(node.val).toString());//1
return;
}
//非叶子节点
//先加上节点的值，再在结果上加个箭头（证明后面还有值连接）
String tmp = new StringBuilder(s).append(node.val).append("->").toString();
//然后开始左右子树递归
path(node.left, tmp);
path(node.right, tmp);
}
}
1、
result.add(new StringBuilder(s).append(node.val).toString())：如果当前节点是叶子节点，那么将从根节点到当前叶子节点的路径添加到结果列表result中。new StringBuilder(s)：创建一个新的StringBuilder对象，以当前路径字符串s为初始内容。s是之前递归过程中累积的从根节点到当前节点的路径字符串。.append(node.val)：将当前叶子节点的值追加到StringBuilder对象中。因为这是叶子节点，所以它的值是路径的最后一个节点。.toString()：将StringBuilder对象转换为字符串，以便将其添加到结果列表result中。
return：在处理完叶子节点后，返回上一层递归。因为叶子节点没有子节点可以继续遍历，所以在这里结束当前递归分支。
三、#404.左叶子之和
关键思路：后序
左叶子的定义：首先他必须是个叶子，接着他必须是其父节点的左节点
此题特殊在：要通过父节点去判断，我们当前收集的节点是不是符合题意的节点
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if(root == null) return 0;
int leftValue = sumOfLeftLeaves(root.left);
int rightValue = sumOfLeftLeaves(root.right);
//存储此次递归到的左叶子节点的值
int mid=0;
if(root.left != null && root.left.left == null && root.left.right == null){
mid = root.left.val;
}
//累加这次和之前递归的和
int sum = mid + leftValue + rightValue;
return sum;
}
}
尝试过程：最终返回结果不对
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
int result = 0;
if(root == null) return 0;
if(root.left == null && root.right == null) return 0;
int left = sumOfLeftLeaves(root.left);
if(root.left != null && root.left.left == null && root.left.right == null){
return result += left;
}
int right = sumOfLeftLeaves(root.right);
if(root.left!=null && root.left.left == null && root.left.right == null){
return result += right;
}
return result;
}
}
//最终返回结果不对
四、#222.完全二叉树的节点个数
关键思路：后序；判断完全二叉树的方式，利用完全二叉树节点数量公式
普通二叉树解法：
class Solution {
public int countNodes(TreeNode root) {
return getNum(root);
}
private int getNum(TreeNode node){
if(node == null) return 0;
return getNum(node.left) + getNum(node.right) +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;
}
return countNodes(root.left) + countNodes(root.right) +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(root.left.left != null){
TreeNode left = root.left.left.left;
leftDepth++;
}
while(root.right.right != null){
TreeNode right = root.right.right.right;
rightDepth++;
}
if(leftDepth == rightDepth){
return (2<<leftDepth) -1;
}
return countNodes(root.left) + countNodes(root.right) +1;
}
}
超时原因：
- 错误的深度计算：
在计算左子树深度时，你使用了 TreeNode left = root.left.left.left; 这行代码，这实际上是在每次循环中重新指向了 root.left.left.left，而不是逐步向下遍历左子树。正确的做法应该是 root = root.left;，然后在循环条件中检查 root != null。
同样地，右子树深度的计算也有类似的问题。
- 不必要的节点访问：
你在计算深度时，每次都访问了 root.left.left 和 root.right.right，这会导致不必要的节点访问，增加了时间复杂度。
- 位运算错误：
你在计算完全二叉树的节点数时，使用了 (2<<leftDepth) - 1，这里的 << 是左移操作符，实际上应该是 (1 << (leftDepth + 1)) - 1，因为完全二叉树的节点数是 2^(depth) - 1。