基本信息

  • 题号：144
  • 题厂：广义模板
  • 难度系数：低


preorder 顺序遍历二叉树


例如 root = [1,null,2,3]
返回 [1,2,3]


解题思路

  • preorder 遍历顺序：节点 - 左节点 - 右节点

# 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 = []
        # 创建 dfs 方法，按照节点-左-右的顺序遍历
        def dfs(node):
            if node:
                res.append(node.val)
                dfs(node.left)
                dfs(node.right)
                
        dfs(root)
        
        return res

# stack mu ban

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        stack = [root]
        # 创建 stack，按照 节点-右-左 顺序放入
        while stack:
            node = stack.pop()
            if node:
                res.append(node.val)
            if node and node.right:
                stack.append(node.right)
            if node and node.left:
                stack.append(node.left)
                
        return res
两种方法遍历后，貌似采用「stack」模式更快捷


Constraints

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100


Big O

  • 时间复杂度：O（n）所有节点轮一遍
  • 空间复杂度：O（logn）stack 的长度为树的高度，即 log n



测试

  • 当树只有一个节点时
  • 当树没有节点时

……


总结

  • 这道题都不会做，可以直接回家歇菜了
  • 虽然这是一道简单题，但是 DFS（深度查找）系列的基础模板——考点无数的 DFS BFS 均由此题发展演变……所以本题作为 DFS 核心思想定期复习熟练操作！！！！
  • 对于 DFS 的两种遍历模式 stack 和 recursion 也要烂熟于心，涉及的 bigO 也要了如指掌
  • 在复习 DFS preorder 的同时，还可以顺带把对应的 BFS Queue，以及系列的 inorder 和 postorder 也一起巩固复习一次
  • 考试时多半不会遇上这种模板基础题。但是如果小概率事件遇上了，只有 10 分钟内熟练解题且 「bug free」才能通关！！！