算法训练营day14 | {110.平衡二叉树, 257.二叉树的所有路径, 404.左叶子之和, 222.完全二叉树的节点个数}

第六章二叉树part03，思考什么题目适用什么遍历方式，练习递归三部曲。

110. 平衡二叉树

1.1 看完代码随想录的想法

  • 平衡二叉树的定义：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。
  • 因为是要求高度，所以用后序遍历比较合适，接着来思考思考递归三部曲：
    1. 参数是什么？返回值是什么？ 传入一个节点，返回以这个节点为根节点的树的高度，如果这个树已经不平衡了，就返回-1。（体会后序遍历的好处）
    2. 确定终止条件。 当传入的节点是空时，返回高度为0。
    3. 确定单层递归的逻辑。 左右中，求该节点左子树和右子树的高度，如果某一个子树已经不平衡了，就不需要再计算另外一边，也不应该继续参与高度计算，剪枝！！然后判断两个子树的高度差是否大于1，如果大于一，那以该节点为子树的节点已经不平衡了，返回-1；否则符合平衡二叉树的定义，本层树的高度正常加1。
  • 迭代法本轮精力有限，不去掌握了。

1.2 解题小结

  • 第一遍写题没有考虑如果某一个子树已经不平衡的情况，导致计算了错误的高度差。修正了。
  • 后序遍历
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    public class Solution {
        public boolean isBalanced(TreeNode root) {
            return getDepth(root) != -1;
        }

        public int getDepth(TreeNode node) {
            if(node == null) return 0;
            int leftHeight = getDepth(node.left);
            if (leftHeight == -1) return -1;
            int rightHeight = getDepth(node.right);
            if (rightHeight == -1) return -1;
            if(Math.abs(leftHeight - rightHeight) > 1) return -1;
            return 1 + Math.max(leftHeight, rightHeight);
        }
    }

257. 二叉树的所有路径

2.1 看完视频的想法

  • 视频给的是不隐藏回溯过程的代码写法，一些网上精简的题解会把回溯的过程隐藏掉（藏在函数调用时的参数赋值里）。

  • 分析递归三部曲

    1. 参数和返回值是什么？ 要传入根节点，记录一条路径用的数组path，和所有结果集的result，不需要返回值。
    2. 确定递归的终止条件。 当遍历到叶子节点递归终止，此时把path加入结果集。
    3. 确定单层递归的逻辑。 按照前序遍历（中左右）的顺序，遍历到哪个节点，就把哪个节点加入path路径，接着遍历左子树，遍历出来的时候要对path进行回溯，遍历右子树也是一样的要回溯。

  • 细节

    1. 在写递归的时候，终止条件习惯了这么写：
      1
      2
      3
      if (cur == null) {
          终止处理逻辑
      }
      但是本题的终止条件这么写会很麻烦，因为null不一定是到了叶子节点，不如在找到叶子节点时，开始结束的处理逻辑。
    2. 回溯和递归是一一对应的，有一个递归，就要有一个回溯。

2.2 解题小结

  • 前序遍历–递归+回溯
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    class Solution {
        public List<String> binaryTreePaths(TreeNode root) {
            List<String> ans = new ArrayList<>();
            LinkedList<String> path = new LinkedList<>();
            preOrder(root, path, ans);
            return ans;
        }

        public void preOrder(TreeNode node, LinkedList<String> path, List<String> result) {
            path.offerLast(String.valueOf(node.val));  // 中
            if (node.left == null && node.right == null) {
                result.add(String.join("->", path));
                return;
            }
            if (node.left != null) {
                preOrder(node.left, path, result);
                path.pollLast();
            }
            if (node.right != null) {
                preOrder(node.right, path, result);
                path.pollLast();
            }
        }
    }

404. 左叶子之和

3.1 看完视频的想法

  • 判断一个叶节点是否是左叶子节点的思路，要借助其父节点，和我想得一样。
  • 本题适用于后序遍历，左右中，让根节点收集其左子树的左叶子之和和右子树的左叶子之和。分析递归三部曲：
    1. 参数和返回值是什么？ 要传入根节点，返回值是这个二叉树的左叶子之和。
    2. 确定递归的终止条件。 当节点为空时，返回0，当节点本身为叶子节点时，也返回0。
    3. 确定单层递归的逻辑。 当遇到左叶子节点时，记录数值。然后通过递归求取左子树左叶子之和，和右子树左叶子之和，相加便是整个树的左叶子之和。

3.2 解题小结

  • 后序遍历–递归法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    class Solution {
        public int sumOfLeftLeaves(TreeNode root) {
            if (root == null) return 0;
            if (root.left == null && root.right == null) return 0;
            int leftSum = sumOfLeftLeaves(root.left);
            if (root.left != null && root.left.left == null && root.left.right == null) leftSum = root.left.val;
            int rightSum = sumOfLeftLeaves(root.right);
            return leftSum + rightSum;
        }
    }

  • 层序遍历-BFS

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution {
        public int sumOfLeftLeaves(TreeNode root) {
            int sum = 0;
            Deque<TreeNode> queue = new ArrayDeque<>();
            if(root != null) queue.offerLast(root);
            while(!queue.isEmpty()) {
                int size = queue.size();
                int curSum = 0;
                while(size-- > 0) {
                    TreeNode node = queue.pollFirst();
                    if(node.left != null) {
                        if(node.left.left == null && node.left.right == null) curSum += node.left.val;
                        queue.offerLast(node.left);
                    }
                    if(node.right != null) queue.offerLast(node.right);
                }
                sum += curSum;
            }
            return sum;
        }
    }

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

4.1 解题分析

  • 自己先分析一下递归三部曲（利用完全二叉树的性质）：

    1. 参数和返回值是什么？ 要传入根节点，返回以该节点为根节点的完全二叉树节点个数。
    2. 确定递归的终止条件。 当节点为空时，返回0；当以该节点为根节点的二叉树是一个满二叉树时，也作为终止条件。
    3. 确定单层递归的逻辑。 后序遍历，左右中，中间节点+1返回。

  • 在写递归算法的时候，遇到一个关键问题：如何判断一个左子树或者右子树是否是二叉树呢？（看视频了）

    • 一直向左、一直向右遍历，如果深度相同，则一定是一个满二叉树，可以画图分析。

4.2 解题小结

  • 普通二叉树-后序遍历

和昨天做过的求树的最大深度、最小高度是一个模板。

1
2
3
4
5
6
class Solution {
    public int countNodes(TreeNode root) {
        if(root == null) return 0;
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}
  • 普通二叉树-层序遍历（BFS）

这样动脑最少，但每个节点都要遍历，效率很低。而判断满二叉树可以减少对中间节点的遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int countNodes(TreeNode root) {
        int result = 0;
        Deque<TreeNode> queue = new ArrayDeque<>();
        if (root != null) queue.offerLast(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                TreeNode node = queue.pollFirst();
                result++;
                if (node.left != null) queue.offerLast(node.left);
                if (node.right != null) queue.offerLast(node.right);
            }
        }
        return result;
    }
}
  • 完全二叉树-后序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        int depth = isFullBinaryTree(root);
        if(depth != -1) return (int)Math.pow(2, depth) - 1;

        int leftCnt = countNodes(root.left);
        int rightCnt = countNodes(root.right);
        return leftCnt + rightCnt + 1;
    }

    public int isFullBinaryTree(TreeNode node) {
        TreeNode left = node.left;
        TreeNode right = node.right;
        int leftDepth = 0, rightDepth = 0;
        while (left != null) {
            left = left.left;
            leftDepth++;
        }
        while (right != null) {
            right = right.right;
            rightDepth++;
        }
        if (leftDepth == rightDepth) {
            return leftDepth + 1;
        } else return -1;
    }
}

5. 今日收获

  • 求树的深度，可以转换为求根节点的高度，进而适用于后序遍历解题，今天继续练习了递归三部曲，然后遇到题目多思考怎么做为什么。
  • 左叶子之和这道题，单层递归逻辑二刷时还需要自己来一遍哦。
  • 学习时长：3小时
Leetcode > 二叉树
#Java #代码随想录
算法训练营day14 | {110.平衡二叉树, 257.二叉树的所有路径, 404.左叶子之和, 222.完全二叉树的节点个数}
http://paopaotangzu.xyz/cn/day14_leetcode/
作者
PROTON TANG
发布于
2026年1月1日
许可协议