算法刷题（一） - 二叉树遍历

发表于 | 阅读次数：

以前刷过的题基本全忘光了，准备投暑期实习开始临时抱佛脚，赶紧复习起来。

二叉树前/中/后序遍历

口诀
前序遍历：根——左——右
中序遍历：左——根——右
后序遍历：左——右——根
前中后就是根节点的顺序

这三种类型的遍历思路都是深度优先搜索（DFS），用递归法比较简单。代码以中序搜索为例，都是定义一个递归嵌套函数，不同顺序只要调换函数中语句执行位置就好了。 

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

二叉树层序遍历

层序遍历的思路是广度优先搜索（BFS），需要维护一个队列，把遍历到的节点 pop 出来，待遍历的节点（当前节点的左右节点）添加到队列末尾。

Leetcode 102 这题比较麻烦的地方在于要求输出嵌套 list 显示二叉树的层级，思路是记录每一层节点的数量，用循环将这一层的节点一次性全部 pop 出来后再开始遍历下一层。 

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

之前写过一个更复杂的版本，队列记录每个节点和对应层级的 tuple，再用一个变量记录每一个 list 的最后一个节点层级。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        queue = [(root, 1)]
        ans = []
        temp = []
        cur_level = 1
        if not root:
            return ans
        while len(queue) > 0:
            cur, level = queue.pop(0)
            if cur.left:
                queue.append((cur.left, level+1))
            if cur.right:
                queue.append((cur.right, level+1))
            if cur_level < level:
                ans.append(temp)
                temp = []
                cur_level += 1
            temp.append(cur.val)
        ans.append(temp)
        return ans

二叉树层序遍历-II

在层序遍历的基础上，要求将奇数层的值正向输出，偶数层反向输出，很容易想到对记录偶数层的数据进行翻转。 

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:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        queue = [root]
        ans = []
        temp = []
        level = 0
        if not root:
            return ans
        while queue:
            length = len(queue)
            odd = True if level % 2 == 1 else False
            for i in range(length):
                node = queue.pop(0)
                temp.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            if odd:
                temp = temp[::-1]
            level += 1
            ans.append(temp)
            temp = []
        return ans
> 可以不使用level对层数进行记录，len(ans)效果相同，但没想到

另一种方法是temp使用双端队列，python中为collections.deque，将奇数层的val添加至队尾，偶数层则用appendleft方法添加至队首