树的遍历
01 / 一句话本质
任何树的遍历算法都会恰好访问每个节点一次 —— 唯一变化的,是"访问"发生在对子节点递归下降的哪一刻。
题目按指定顺序遍历一棵二叉树二叉树[1, 2, 3, 4, 5, ·, 6]遍历前序
输出—— 暂无 ——
深度优先 —— 前序在向子节点递归之前访问节点。
步
0 / 7
正在访问
—
已访问
0 / 6
遍历
前序
0 / 7
02 / 模式骨架
# 深度优先 —— 三种变体只是"访问"放在不同位置traverse(node):if node is null: returnvisit(node) // 前序traverse(node.left)visit(node) // 中序traverse(node.right)visit(node) // 后序# 广度优先 —— 迭代,基于队列level_order(root):q ← [root]while q not empty:node ← q.dequeue(); visit(node)enqueue node.left, node.right
03 / 什么时候用这个模式
"BST 的中序"
二叉搜索树的有序输出来自中序 —— 这是 BST 的性质, 并不是中序遍历本身的一般性质。
"逐层"
需要按行处理整棵树 —— 节点深度、锯齿形输出、"找树的右视图"等等。 基于队列的层序正是这件工具。
"自底向上 / 先子后父"
只有先知道子节点的答案,才能算出当前节点的答案 —— 子树和、高度、路径等。后序能保证子节点先被访问。
"序列化 / 克隆"
把一棵树写成字符串,或是逐节点复制。常用前序外加显式的 null 标记 —— 这样能无歧义地刻画结构。
04 / 常见坑
该用后序时用了中序。
任何需要根据子节点答案推父节点答案的事情 —— 子树和、高度、直径 —— 都必须在父节点之前访问子节点。这就是后序。 中序会让部分子节点访问得太晚。
漏掉判空。
递归遍历的第一行就是
if node is null: return。 漏掉它,就会在每个叶子缺失的子节点处解引用 null。 动画把这点显式呈现 —— 空子树根本不渲染。把调用栈当成输出顺序。
递归天然的调用栈并不是访问的顺序。一个节点会在自己前序访问之前就压入栈, 直到后序访问之后才弹出 —— 这是同一节点的三个不同"时刻"。
05 / 去 LeetCode 上练习
简单21
01Binary Tree Inorder Traversal— LC 94→02Same Tree— LC 100→03Symmetric Tree— LC 101→04Maximum Depth of Binary Tree— LC 104→05Balanced Binary Tree— LC 110→06Minimum Depth of Binary Tree— LC 111→07Path Sum— LC 112→08Binary Tree Preorder Traversal— LC 144→09Binary Tree Postorder Traversal— LC 145→10Count Complete Tree Nodes— LC 222→11Invert Binary Tree— LC 226→12Binary Tree Paths— LC 257→13Sum of Left Leaves— LC 404→14Diameter of Binary Tree— LC 543→15Maximum Depth of N-ary Tree— LC 559→16Subtree of Another Tree— LC 572→17Merge Two Binary Trees— LC 617→18Search in a Binary Search Tree— LC 700→19Minimum Distance Between BST Nodes— LC 783→20Range Sum of BST— LC 938→21Cousins in Binary Tree— LC 993→
中等42
01Validate Binary Search Tree— LC 98→02Recover Binary Search Tree— LC 99→03Binary Tree Level Order Traversal— LC 102→04Binary Tree Zigzag Level Order Traversal— LC 103→05Construct Binary Tree from Preorder and Inorder Traversal— LC 105→06Construct Binary Tree from Inorder and Postorder Traversal— LC 106→07Binary Tree Level Order Traversal II— LC 107→08Path Sum II— LC 113→09Sum Root to Leaf Numbers— LC 129→10Binary Search Tree Iterator— LC 173→11Binary Tree Right Side View— LC 199→12Kth Smallest Element in a BST— LC 230→13Lowest Common Ancestor of a Binary Search Tree— LC 235→14Lowest Common Ancestor of a Binary Tree— LC 236→15Binary Tree Vertical Order Traversal— LC 314→16House Robber III— LC 337→17N-ary Tree Level Order Traversal— LC 429→18Path Sum III— LC 437→19Serialize and Deserialize BST— LC 449→20Delete Node in a BST— LC 450→21Convert BST to Greater Tree— LC 538→22Maximum Width of Binary Tree— LC 662→23Insert into a Binary Search Tree— LC 701→24Smallest Subtree with all the Deepest Nodes— LC 865→25Construct Binary Tree from Preorder and Postorder Traversal— LC 889→26Distribute Coins in Binary Tree— LC 979→27Smallest String Starting From Leaf— LC 988→28Construct Binary Search Tree from Preorder Traversal— LC 1008→29Binary Search Tree to Greater Sum Tree— LC 1038→30Lowest Common Ancestor of Deepest Leaves— LC 1123→31Tree Diameter— LC 1245→32Smallest Common Region— LC 1257→33Deepest Leaves Sum— LC 1302→34Maximum Product of Splitted Binary Tree— LC 1339→35Longest ZigZag Path in a Binary Tree— LC 1372→36Balance a Binary Search Tree— LC 1382→37Count Good Nodes in Binary Tree— LC 1448→38Diameter of N-Ary Tree— LC 1522→39Lowest Common Ancestor of a Binary Tree II— LC 1644→40Lowest Common Ancestor of a Binary Tree III— LC 1650→41Create Binary Tree From Descriptions— LC 2196→42Most Profitable Path in a Tree— LC 2467→