树的概念及其应用（Python）

1. 树

树是一种由节点（node）和边（edges）构成层级关系的结构。

如果你了解 linux 文件结构（tree 命令），它的结构也是一棵树。

我们快速看下树涉及到的一些概念：

• 根节点(root): 树的最上层的节点，任何非空的树都有一个节点
• 路径(path): 从起始节点到终止节点经历过的边
• 父亲(parent)：除了根节点，每个节点的上一层边连接的节点就是它的父亲(节点)
• 孩子(children): 每个节点由边指向的下一层节点
• 兄弟(siblings): 同一个父亲并且处在同一层的节点
• 子树(subtree): 每个节点包含它所有的后代组成的子树
• 叶子节点(leaf node): 没有孩子的节点成为叶子节点

2. 二叉树

二叉树是树结构里面最常用的一种树结构，其实二叉树就是一种简单的树。

二叉树的每个节点最多包含两个孩子。

从上边的图来看几个二叉树的概念：

• 节点深度(depth): 节点对应的 level 数字。
• 树的高度(height): 二叉树的高度就是 level 数 + 1，因为 level 从 0开始计算的。
• 树的宽度(width): 二叉树的宽度指的是包含最多节点的层级的节点数。
• 树的 size：二叉树的节点总个数。

一棵 size 为 n 的二叉树高度最多可以是 n，最小的高度是 ⌊lgn⌋+1，这里 log 以 2 为底简写为 lgn。

1.1 二叉树的前序遍历

一棵二叉树的前序遍历结果 = 根节点 + 左子树的前序遍历结果 + 右子树的前序遍历结果。

可以理解为有序的遍历二叉树。

class Solution:
    def preorderTraversal(self, root:TreeNode) -> List[int]:
        self.res = []
        self.traverse(root) #从 root 开始遍历
        return self.res # 返回的是 list

    def traverse(self, root: TreeNode):
        if root == None:
            return
            
        self.res.append(root.val) # 前序遍历位置
        self.traverse(root.left)
        self.traverse(root.right)
1
2
3
4
5
6
7
8
9
10
11
12
13

1.2 二叉树的中序遍历

二叉树的中序遍历，一般在二叉搜索树（BST）中最为常用。

你完全可以把 BST 的中序遍历认为是遍历有序数组。

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        self.res = []
        self.traverse(root)
        return self.res

    def traverse(self, root: TreeNode):
        if root == None:
            return

        self.traverse(root.left)
        self.res.append(root.val) #中序遍历位置
        self.traverse(root.right)
1
2
3
4
5
6
7
8
9
10
11
12
13

1.3 二叉树的后序遍历

后序遍历通过递归的返回，返回了二叉树子节点的信息。

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        self.res = []
        self.traverse(root)
        return self.res

    def traverse(self, root: TreeNode):
        if root == None:
            return


        self.traverse(root.left)
        self.traverse(root.right)
        self.res.append(root.val) #后续遍历位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14

1.4 二叉树的应用

对于二叉树的遍历，前序遍历执行是自顶向下的，而后序遍历执行是自底向上的。

以上三种遍历过程是通过递归来实现的，也是 DFS 在二叉树中的应用 。

在应用中，二叉树的递归方法使用可以分两类思路：

• 第一类是直接遍历一遍二叉树，对应前序遍历。
• 第二类是分解问题，变为通过子问题求解，对应后序遍历。

遇到问题是否可以通过遍历一遍二叉树得到答案**（前序遍历）**？

如果不能的话，是否可以通过分解问题，用子问题（子树）的答案推导出原问题的答案**（后序遍历）**。

用几个例子来看一下：

104. 二叉树的最大深度。

求二叉树的最大深度，也就是求这棵树的左右子树深度最大的值，直接遍历二叉树就能解决此问题。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        return self.traverse(root)

    def traverse(self, root):
        if not root:
            return 0
        return max(self.traverse(root.left), self.traverse(root.right)) + 1 # 递归，左右子树的最大深度
        # 加 1 是加上根节点的深度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

543. 二叉树的直径。

根据题目，直径可以理解为任意节点的左右子树的最大深度之和。

那么直接的想法是对每个节点计算左右子树的最大高度，得出每个节点的直径，从而得出最大的那个直径。

解决这题的关键在于，每一条二叉树的直径长度，就是一个节点的左右子树的最大深度之和。

这就是把原问题分解为子问题的方法。

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.max = 0
        self.traverse(root)
        return self.max

    def traverse(self, root):
        if not root:
            return 0
        l = self.traverse(root.left) #求该节点左子树的深度
        r = self.traverse(root.right)#求该节点右子树的深度

        self.max = max(self.max, l+r) # 后续遍历更新最大的直径
        return max(l,r) + 1 #这也是后序遍历的位置。
        					# 由于利用后序遍历从低向上计算子问题，其含义是返回当前节点（子节点）中左右子树深度最大的那一个，用于后续计算最大路径。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15