【代码随想录】二叉树1-遍历

二叉树概念

满二叉树和完全二叉树

二叉搜索树

二叉搜索树是一个有序树。

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 它的左、右子树也分别为二叉排序树

平衡二叉搜索树，又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

存储方式

链式存储：

顺序存储：

如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。

遍历

• 深度优先遍历
  • 前序遍历（递归法，迭代法）
  • 中序遍历（递归法，迭代法）
  • 后序遍历（递归法，迭代法）
• 广度优先遍历
  • 层次遍历（迭代法）

注意，这里前中后，其实指的就是中间节点的遍历顺序，只要大家记住前中后序指的就是中间节点的位置就可以了。

二叉树的递归遍历

迭代（iteration）是重复反馈过程的活动，其目的通常是逼近所需目标或结果；递归（recursion）是重复调用函数自身。迭代通常由计数器来判断是否结束；而递归则满足终止条件才逐层返回。

递归三要素：

• 确定递归函数的参数和返回值：参数为当前节点，返回值为结果数组（在方法内定义迭代函数，可以不设置返回值）
• 确定终止条件：当前节点为空则返回
• 确定单层递归的逻辑：三个步骤，根据遍历的类型来调整顺序
  • 遍历当前节点（将当前节点的内容加到结果数组中）
  • 遍历左子树
  • 遍历右子树

前序遍历代码如下，中序和后序遍历只需要更改递归函数中的逻辑顺序即可

# 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []

        def recursion(node):
            if node != None:
                res.append(node.val)
                recursion(node.left)
                recursion(node.right)
        
        recursion(root)
        return res

二叉树的迭代遍历

递归的实现是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。

前序遍历

当栈不为空时，将栈顶节点 pop，访问其元素，并将其子节点分别放入栈中。注意要先放右节点再放左节点，以保证左节点先访问。

# 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []

        stack = [root]

        while len(stack) != 0:
            cur = stack.pop()
            if cur != None:
                res.append(cur.val)
                stack.append(cur.right)
                stack.append(cur.left)
        
        return res

中序遍历

前序遍历的顺序是中左右，先访问的元素是中间节点（子节点分别放到栈中），先处理的元素也是中间节点（将 val 存入 res），所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。

中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。

对于当前栈顶节点节点，一直遍历左子树，直到为空（访问左）；然后，将 val 存入 res（处理中）；最后再将当前节点的右子树放到栈中（访问右）。

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        stack = []
        cur = root
        while True:
            while cur != None:
                stack.append(cur)
                cur = cur.left
            
            if len(stack) == 0:
                break
            cur = stack.pop()
            res.append(cur.val)
            cur = cur.right

        return res

后续遍历

思路 1

和中序遍历一样，对于当前节点，一直遍历其左子树，直到为空（访问左）；然后对其右子树进行判断（访问右），如果：

• 右子树为空，则访问当前元素（处理中）
• 右子树不为空，此时需要判断当前右子树是否被访问过：
  • 右子树访问过，则访问当前元素
  • 没访问过，则当前节点再次入栈，并且当前指针指向右节点

总结一下，右子树不为空并且没被访问过，则访问右子树；否则访问当前元素，并记录当前元素已经访问。

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

        stack = []
        cur = root
        prev = None

        while True:
            while cur != None:
                stack.append(cur)
                cur = cur.left
            
            if len(stack) == 0:
                break
            
            cur = stack.pop()

            if cur.right != None and prev != cur.right:

                stack.append(cur)
                cur = cur.right
            else:
                res.append(cur.val)
                prev = cur
                cur = None
        return res

思路 2

先序遍历是中左右，后序遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了。

统一迭代遍历

递归本质上是维护一个栈来保存调用顺序。但是可能会面临访问（访问子节点）和处理（读取值）不同步的情况，导致不同的遍历顺序写法不同。要统一写法，将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记：

• 方法一：就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 这种方法可以叫做空指针标记法。

• 方法二：加一个 boolean 值跟随每个节点，false (默认值) 表示需要为该节点和它的左右儿子安排在栈中的位次，true 表示该节点的位次之前已经安排过了，可以收割节点了。 这种方法可以叫做boolean 标记法。这种方法更容易理解，在面试中更容易写出来。

方法一

首先把根节点放到 stack 中（保证不为空），核心逻辑为：栈头元素出栈，判断该节点是否为空

• 如果为空，说明当前的栈头元素的子元素已经访问过，则当前栈头元素出栈，读取其 val；
• 如果不为空，说明当前元素的子元素没被访问过，则将当前节点的子节点、当前节点和一个空节点加入到 stack 中。（注意 stack 先进先出，所以要逆序，即前序遍历是中左右，则放入 stack 的顺序为：右、左，中+空节点）

前序代码如下，中序和后序只需要更改三个步骤的顺序即可。

class Solution:
    
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        stack = []
        if root != None:
            stack.append(root)

        while len(stack) != 0:
            cur = stack.pop()
            if cur != None:
                # 右节点入栈
                if cur.right:
                    stack.append(cur.right)

                # 左节点入栈
                if cur.left:
                    stack.append(cur.left)

                # 中间节点入栈
                stack.append(cur)
                stack.append(None)

            else:
                cur = stack.pop()
                res.append(cur.val)

        return res

方法二

栈存放一个元组，包含节点和一个 flag，表示当前节点的子节点是否被访问过。接下来则和方法一类似，对于每个节点都检查这个 flag，如果为 False，说明子节点没有被访问过，则遍历子节点；如果为 True，则处理当前节点。

# 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []

        stack = []
        if root != None:
            stack.append((root, False))

        while len(stack) != 0:
            cur, flag = stack.pop()
            if flag == False:
                if cur.right:
                    stack.append((cur.right, False))
                if cur.left:
                    stack.append((cur.left, False))
                stack.append((cur, True))

            else:
                res.append(cur.val)
        return res

102.二叉树的层序遍历

link

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

思路

一个队列来存储节点。对于当前节点，访问之后将其子节点加入到队列中，直到队列为空。

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        que = deque()
        res = []
        if root:
            que.append(root)
        
        while que:
            cur = que.popleft()

            res.append(cur.val)

            if cur.left:
                que.append(cur.left)
            if cur.right:
                que.append(cur.right)
        
        return res

不难写出以上代码，但是注意到题目要求每一层的节点在单独的一个 list 中。解决方法，保证每次循环（que 长度不为 0）时，队列中只有一层的节点，所以可以一次性把当前层的所有子节点全部放到队列中。只需要对当前队列进行遍历即可。

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        que = deque()
        res = []
        if root:
            que.append(root)
        
        while que:
            cur_level = []
            for _ in range(len(que)):

                cur = que.popleft()

                cur_level.append(cur.val)

                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)

            res.append(cur_level)
        return res

107.二叉树的层次遍历 II

给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

思路：相较于上一题，只需要把结果反过来即可

199.二叉树的右视图

link

思路：遍历每一层时，只需要保留当前层的最后一个元素即可

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        que = deque()
        res = []
        count = 0
        if root:
            que.append(root)
            count += 1
        
        while que:
            l = len(que)
            for i in range(len(que)):

                cur = que.popleft()
                if i == l - 1:
                    res.append(cur.val)

                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)
        return res

637.二叉树的层平均值

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

思路：遍历每一层时求均值即可

429.N叉树的层序遍历

和二叉树相同，只不过 N 叉树的子节点为一个 Node 的数组

515.在每个树行中找最大值

将每行数组中最大的值存入 res 即可

116.填充每个节点的下一个右侧节点指针

思路：在每一层，针对每一个节点进行操作即可

104.二叉树的最大深度

二叉树的层序遍历，最后返回 res 的长度即可

111.二叉树的最小深度

同样是层序遍历，只不过判断条件是左右孩子全为空则说明到了最浅的节点（因为是严格按照一层一层来进行遍历的）。