数据结构 树(第10-14天)

树的题目太多了，先总结一下树的遍历方式。
按照根节点的遍历顺序。可以分为前序、中序、后序。
前序遍历，即根–>左–>右的顺序。
中序遍历，左–>根–>右。
后续遍历，左–>右–>根。

用递归实现非常简单:
下面是一个前序遍历，核心部分preorder实现了前序遍历。

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def preorder(root):
            nonlocal res
            res.append(root.val)
            if root.left: preorder(root.left)
            if root.right: preorder(root.right)
        if not root: return []
        res = []
        preorder(root)
        return res
1
2
3
4
5
6
7
8
9
10
11

只要改一下访问顺序，就得到中序遍历：

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def inorder(root):
            nonlocal res
            
            if root.left: inorder(root.left)
            res.append(root.val)
            if root.right: inorder(root.right)
        if not root: return []
        res = []
        inorder(root)
        return res
1
2
3
4
5
6
7
8
9
10
11
12

同样可以得到后序遍历：

    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def postorder(root):
            nonlocal res
            
            if root.left: postorder(root.left)
            if root.right: postorder(root.right)
            res.append(root.val)
        if not root: return []
        res = []
        postorder(root)
        return res
1
2
3
4
5
6
7
8
9
10
11

除了这3种遍历，还有一种层序遍历：每次遍历访问一层节点。
可以用队列来实现：

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        queue = [root]
        res = []
        while queue:
            sub_list = []
            for i in range(len(queue)):
                t = queue.pop(0)
                sub_list.append(t.val)
                if t.left:
                    queue.append(t.left)
                if t.right:
                    queue.append(t.right)
            res.append(sub_list)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

剩下的和树相关的题，大多可以用递归实现。（因为树就是一种递归结构）
有很多与二叉搜索树有关。二叉搜索树（BST）是一种特殊的二叉树，也叫二叉排序树，满足左<根<右的特点。处理BST时要利用这个性质。

二叉搜索树（BST），它或者是一棵空树，或者是具有下列性质的 二叉树 ： 若它的左子树不空，则左子树上所有结点的值均小于它的 根结点 的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为 二叉排序树 。