木の走査
01 / 一文で言うと
木の走査アルゴリズムはどれも各ノードをちょうど 1 回ずつ訪れる —— 違うのは、子への再帰的下降のうちで「訪問」がいつ起こるか、その一点だけ。
問題指定の順序で二分木を走査する二分木[1, 2, 3, 4, 5, ·, 6]順序前順
出力—— まだ何もない ——
深さ優先 —— 前順はノードを子への再帰の前に訪れる。
ステップ
0 / 7
訪問中
—
訪問済み
0 / 6
順序
前順
0 / 7
02 / パターンの骨格
# 深さ優先 —— 3 つの変種は「訪問」の位置だけが違う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 / よくある落とし穴
後順が必要なときに中順を使う。
子の答えから親の答えを計算するもの —— 部分木の和、高さ、直径 —— は 必ず親より前に子を訪れる必要がある。それが後順。 中順では一部の子が訪れるのが遅すぎる。
null チェックを忘れる。
再帰走査の最初の行が
if node is null: return。 これを抜くと、葉ノードの存在しない子ごとに null を参照してしまう。 アニメーションではこれを明示している —— 空の部分木はそもそも描かれない。呼び出しスタックを出力の順序と混同する。
再帰の自然な呼び出しスタックは訪問の順序ではない。 1 つのノードは前順訪問の前から後順訪問の後までスタックに乗っている —— 同じノードの 3 つの異なる「瞬間」。
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→