代码随想录算法训练营第十五天

目录

LeetCode.110 平衡二叉树

题目链接 平衡二叉树

题解

解题思路

LeetCode.257 二叉树的所有路径

题目链接 二叉树的所有路径

题解

解题思路

LeetCode.404 左叶子之和

题目链接 左叶子之和

题解

解题思路

LeetCode.222 完全二叉树的节点个数

题目链接  完全二叉树的节点个数

题解

解题思路

LeetCode.110 平衡二叉树

题目链接 平衡二叉树

题解

class Solution {
    public boolean isBalanced(TreeNode root) {
        int h = getHeight(root);
        if(h == -1){
            return false;
        }
        return true;
    }
    public 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;
        int result = 0;
        if(Math.abs(rightHeight - leftHeight) > 1){
           result = -1;
        }else {
            result = Math.max(rightHeight,leftHeight) + 1;
        }
        return result;
    }
}

解题思路

这是一道判断二叉树是否为平衡二叉树的题目，核心是递归计算子树高度并检查平衡性，思路拆解如下：

1. 平衡二叉树定义：

   • 每个节点的左右子树的高度差不超过 1，且左右子树均为平衡二叉树。

2. 递归辅助函数 getHeight：

   • 返回值含义：
     • 若子树平衡，返回子树的高度（常规递归计算）。
     • 若子树不平衡，返回 -1 表示 “剪枝”，提前终止后续计算。
   • 递归流程：
     1. 终止条件：若节点为空，返回高度 0。
     2. 递归计算左子树高度 leftHeight，若为 -1 直接返回 -1。
     3. 递归计算右子树高度 rightHeight，若为 -1 直接返回 -1。
     4. 检查当前节点的左右子树高度差是否超过 1：
        • 若超过，返回 -1。
        • 否则，返回当前子树的高度 max(leftHeight, rightHeight) + 1。

3. 主函数 isBalanced：

   • 调用 getHeight(root)，若返回值为 -1 则树不平衡，否则平衡。

核心逻辑：

• 通过后序遍历（左右根）的方式，自底向上计算子树高度并检查平衡性。
• 一旦发现某子树不平衡，立即返回 -1 快速 “剪枝”，避免无效计算。

LeetCode.257 二叉树的所有路径

题目链接 二叉树的所有路径

题解

class Solution {
    List<String> resList = new ArrayList<>();
 
    public List<String> binaryTreePaths(TreeNode root) {
        if(root == null){
            return resList;
        }
        StringBuilder sb = new StringBuilder(String.valueOf(root.val));
        getPath(root,sb);
        return resList;
    }
    public void getPath(TreeNode node,StringBuilder sb){
        if(node.left == null && node.right == null){
            resList.add(sb.toString());
            return ;
        }
        if(node.left != null){
            StringBuilder leftSb = new StringBuilder(sb);
            leftSb = leftSb.append("->").append(node.left.val);
            getPath(node.left,leftSb);
        }
        if(node.right != null){
            StringBuilder rightSb = new StringBuilder(sb);
            rightSb = rightSb.append("->").append(node.right.val);
            getPath(node.right,rightSb);
        }

    }
}

解题思路

这是一道枚举二叉树所有根到叶子路径的题目，核心是回溯法遍历所有路径，思路拆解如下：

1. 路径记录：

   • 使用 StringBuilder 动态构建路径字符串，初始时包含根节点的值。

2. 递归回溯：

   • 终止条件：若当前节点是叶子节点（无左右子树），将当前路径加入结果列表 resList。
   • 递归过程：
     • 左子树：复制当前路径 sb，添加左子节点的值，递归处理左子树。
     • 右子树：复制当前路径 sb，添加右子节点的值，递归处理右子树。
   • 关键点：每次递归前复制 sb，确保左右子树路径独立（避免路径污染）。

3. 复杂度：

   • 时间复杂度：O (n log n)，每个节点遍历一次，路径字符串拼接时间与树高相关。
   • 空间复杂度：O (n log n)，存储所有路径的字符串。

执行流程：

• 从根节点开始，递归遍历每个节点，动态构建路径。
• 到达叶子节点时记录路径，非叶子节点则分别处理左右子树。
• 通过复制 StringBuilder 保证各路径独立，最终返回所有路径的集合。

LeetCode.404 左叶子之和

题目链接 左叶子之和

题解

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null) return 0;
        int leftN = sumOfLeftLeaves(root.left);
        int rightN = sumOfLeftLeaves(root.right);
        int res = 0;
        if(root.left != null && root.left.left == null && root.left.right == null){
            res += root.left.val;
        }
        res = res + leftN + rightN;
        return res; 
    }
}

解题思路

这是一道计算二叉树所有左叶子节点值之和的题目，核心是递归遍历并判断左叶子节点，思路拆解如下：

1. 左叶子节点定义：

   • 必须是左子节点，且自身是叶子节点（无左右子树）。

2. 递归遍历：

   • 终止条件：若当前节点为空，返回 0。
   • 递归计算：
     • 左子树：递归计算 sumOfLeftLeaves(root.left)。
     • 右子树：递归计算 sumOfLeftLeaves(root.right)。
   • 结果累加：
     • 若当前节点的左子节点是叶子节点，将其值累加到结果 res 中。
     • 最终结果为 res + 左子树结果 + 右子树结果。

3. 关键点：

   • 判断左叶子节点的条件：root.left != null && root.left.left == null && root.left.right == null。
   • 递归遍历右子树时，即使右子树存在叶子节点，也不参与累加（题目仅关注左叶子）。

执行流程：

• 从根节点开始递归，逐层向下检查每个节点。
• 若当前节点的左子节点是叶子节点，记录其值。
• 递归处理左右子树，累加所有符合条件的左叶子节点值。

LeetCode.222 完全二叉树的节点个数

题目链接  完全二叉树的节点个数

题解

class Solution {
    public int countNodes(TreeNode root) {
        if(root == null){
            return 0;
        }
        int leftN = countNodes(root.left);
        int rightN = countNodes(root.right);
        return 1 + leftN + rightN;
    }
}

解题思路

将大问题分成小问题。