团灭二叉树遍历

二叉树遍历常见的3中遍历方式：「二叉树的前序遍历」、「二叉树的中序遍历」 和 「二叉树的后续遍历」，此外按照层序方式（按照层次从上至下，每一层从左至右）对二叉树进行遍历，这种方式叫做 「二叉树的层序遍历」。下面分别介绍二叉树的递归解法和迭代解法。

1. 递归解法

144. 二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的前序遍历。

示例 1：

1 2	输入：root = [1,null,2,3] 输出：[1,2,3]

代码（递归解法）：

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root: return []
        res = []

        def preorder(root):
            if not root: return  #1.判断二叉树是否为空，为空则直接返回。
            res.append(root.val) #2.先访问根节点。
            preorder(root.left)  #3.然后递归遍历左子树。
            preorder(root.right) #4.最后递归遍历右子树。
        
        preorder(root)
        return res

94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的中序遍历 。

示例 1：

1 2	输入：root = [1,null,2,3] 输出：[1,3,2]

代码（递归解法）：

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

        def inorder(root):
            if not root: return
            inorder(root.left)
            res.append(root.val)
            inorder(root.right)
        inorder(root)
        return res

145. 二叉树的后序遍历

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例 1：

1 2	输入：root = [1,null,2,3] 输出：[3,2,1]

代码(递归解法):

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        def postorder(root):
            if not root: return
            postorder(root.left)
            postorder(root.right)
            res.append(root.val)
        postorder(root)
        return res

2. 迭代解法（颜色标记法）

颜色标记法的核心思想如下：

用颜色标记节点的状态，新节点为白色，已访问节点为灰色
如果遇到未访问的节点，则将其标记为白色，然后将左子节点，右子节点，自身节点压入栈中
如果遇到的节点为灰色，则将节点的值输出

144. 二叉树的前序遍历

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        WHILE,GRAY = 0,1
        res = []
        stack = [(WHILE,root)]
        while stack:
            color,node = stack.pop()
            if not node: continue
            if color == WHILE:
                stack.append((WHILE,node.right))
                stack.append((WHILE,node.left))
                stack.append((GRAY,node))
            if color==GRAY:
                res.append(node.val)
        return res

94. 二叉树的中序遍历

def inorderTraversal(self, root: TreeNode) -> List[int]:
        WHITE, GRAY = 0, 1
        res = []
        stack = [(WHITE, root)]  # 这里把第一个节点直接定义为白色
        while stack:
            color, node = stack.pop()
            if node is None: continue
            if color == WHITE:
              # 因为使用的栈，所以在这里添加顺序是右，根，左，
           		# 遵守了栈的后进先出结构，只需要随意改变顺序，便可以
           		# 实现二叉树的前序，中序，后序遍历
                stack.append((WHITE, node.right))
                stack.append((GRAY, node))
                stack.append((WHITE, node.left))
            else:
                res.append(node.val)
        return res

145. 二叉树的后序遍历

def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        WHITE,GRAY = 0,1
        stack = [(WHITE,root)]
        while stack:
            color,node = stack.pop()
            if node is None: continue
            if color == WHITE:
              	# 在这里添加顺序是根，右，左，
                stack.append((GRAY,node))
                stack.append((WHITE, node.right))
                stack.append((WHITE, node.left))
            if color == GRAY:
                res.append(node.val)
        return res

102. 二叉树的层序遍历

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

示例 1：

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

颜色标记法：

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:

        res = []
        if not root: return res
        WHITE,GRAY = 0,1
        stack = [(root,WHITE,0)] # 包含三个变量，节点，标记符，节点层数
        while stack:
            node,color,level = stack.pop()
            if not node: continue
            if color==WHITE:
                stack.append((node.right,WHITE,level+1))
                stack.append((node.left,WHITE,level+1)) 
                stack.append((node,GRAY,level)) # 当前节点已使用
            else:
                if level ==len(res):
                    res.append([])
                res[level].append(node.val)
        return res

103. 二叉树的锯齿形层序遍历

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例 1：

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

分析：层次遍历的变种，比较简单。

class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        if not root: return res
        stack = [(root,0,0)] # 节点，标记符，层数
        while stack:
            node,flag,level = stack.pop()
            if not node: continue
            if not flag:
                stack.append((node.right,0,level+1))
                stack.append((node.left,0,level+1))
                stack.append((node,1,level))
            else:
                if level == len(res): res.append([])
                res[level].append(node.val)

        for i in range(len(res)): # 偶数级做一次翻转
            if (i+1)%2==0: res[i].reverse()
        return res

107. 二叉树的层序遍历 II

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

示例 1：

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

分析：和层次遍历一样的做法，只需要将得到的res数组做一次处理既可。