二叉树的遍历

目录

定义树节点

前序遍历，或称先序遍历

中序遍历

后序遍历

定义树节点

# 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: TreeNode) -> List[int]:
        # 二叉树的前序遍历Preorder Traversal (VLR)，又称先序遍历、先根遍历
        res = []
        stack = []
        stack.append(root) # 根节点入栈

        while stack: # stack 非空时，说明树还没有遍历完毕
            cur_node = stack[-1]
            stack.pop()
            if cur_node is None:
                continue
            res.append(cur_node.val) # 由于前序遍历，所以先把根节点的val加入ans
            stack.append(cur_node.right) # 栈先进后出，所以前序遍历时，右节点先进后出
            stack.append(cur_node.left) # 同理，左节点后进先出
        return res

中序遍历

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        # 中序相较于前序(直接按根的右左顺序压入栈中)，多了一层循环，用于push直到最左边才停止
        # 初始化
        res = []
        stack = []
        cur_node = root
        # 循环
        while stack or cur_node:
            while cur_node: # 一直找到最左侧的叶节点
                stack.append(cur_node) # 从顶到底，每个左子树入栈
                cur_node = cur_node.left
            cur_node = stack.pop()
            res.append(cur_node.val)
            cur_node = cur_node.right
        return res

后序遍历

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        # 类似于先序遍历，但是最后用插入的方式，所以先push左节点，再push右节点
        res = []
        stack = []
        stack.append(root)
        while stack:
            cur_node = stack.pop()
            if cur_node is None:
                continue
            stack.append(cur_node.left)
            stack.append(cur_node.right)

            res.insert(0, cur_node.val) # 插入
        return res