代码随想录算法训练营第十三天 | 二叉树 Part03

618 字

3 分钟

代码随想录算法训练营第十三天 | 二叉树 Part03

2025-06-25

算法

平衡二叉树、二叉树的所有路径、左叶子之和、完全二叉树的节点个数

/

算法

/

LeetCode

/

Python

二叉树前序遍历（根-左-右）#

一般用于需要先处理根节点的场景。
典型应用：
- 复制一棵树（先创建根节点，再递归复制子树）。
- 序列化和反序列化二叉树。
- 先序表达式计算。

二叉树中序遍历（左-根-右）#

适合需要按顺序处理节点的场景。
典型应用：
- 二叉搜索树的排序，因为中序遍历得到的是排序后的节点值序列。
- 验证一棵树是否为二叉搜索树（中序遍历结果是否单调递增）。
- 构建有序数据结构。

二叉树后序遍历（左-右-根）#

适合需要先处理子节点的场景。
典型应用：
- 删除一棵树（先删除子节点，再删除根节点，避免内存泄漏）。
- 计算子树相关信息后再更新根节点，如计算树的高度、判断平衡性。
- 表达式树的后缀表达式计算。

110. 平衡二叉树#

LeetCode 110. 平衡二叉树

1
class Solution:
2
    # 因为处理子节点的场景，所以使用后序遍历
3
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
4
        # 调用辅助函数获取高度，若返回-1表示不平衡
5
        return self.get_height(root) != -1
6

7
    def get_height(self, root):
8
        if not root:
9
            return 0
10
        left = self.get_height(root.left)
11
        if left == -1:
12
            return -1
13
        right = self.get_height(root.right)
14
        if right == -1:
15
            return -1
16
        if abs(left - right) > 1:
17
            return -1
18
        else:
19
            return max(left, right) + 1

257. 二叉树的所有路径#

LeetCode 257. 二叉树的所有路径

1
class Solution:
2
    # 因为处理子节点的场景，所以使用后序遍历
3
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
4
        res = []
5
        path = []
6
        if not root:
7
            return res
8
        path.append(root.val)
9
        self.traverse(root, path, res)
10
        return res
11

12
    def traverse(self, root, path, res):
13
        # 到达叶子节点，路径加入结果
14
        if not root.left and not root.right:
15
            sPath = '->'.join(map(str, path))
16
            res.append(sPath)
17
            return
18
        # 遍历左子树
19
        if root.left:
20
            path.append(root.left.val)
21
            self.traverse(root.left, path, res)
22
            path.pop()
23
        # 遍历右子树
24
        if root.right:
25
            path.append(root.right.val)
26
            self.traverse(root.right, path, res)
27
            path.pop()

404. 左叶子之和#

LeetCode 404. 左叶子之和

1
class Solution:
2
    # 处理子节点的场景，所以使用后序遍历
3
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
4
        if not root:
5
            return 0
6
        left = self.sumOfLeftLeaves(root.left)
7
        # 判断左子节点是否为叶子节点
8
        if root.left and not root.left.left and not root.left.right:
9
            left = root.left.val
10
        right = self.sumOfLeftLeaves(root.right)
11
        sum_val = left + right
12
        return sum_val

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

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

1
class Solution:
2
    # 因为处理子节点的场景，所以使用后序遍历
3
    def countNodes(self, root: Optional[TreeNode]) -> int:
4
        return self.traverse(root)
5

6
    def traverse(self, root):
7
        if not root:
8
            return 0
9
        left = self.traverse(root.left)
10
        right = self.traverse(root.right)
11
        sum_val = left + right + 1
12
        return sum_val