[ Leetcode ] Binary Tree - Traversal

nofear195 included in Leetcode

2024-04-08 2024-04-24 About 1300 words 3 minutes - views - comments

Contents

Operations

Definition

1
2
3
4
5
class TreeNode:
  def __init__(self, val = 0, left = None, right = None):
      self.val = val
      self.left = left
      self.right = right

Way of Traversal

Depth-first traversal:
- 先往深度走，遇到 leaf node 再往回走
- Inorder traversal (左中右)
- Preorder traversal (中左右)
  - 隱含由當前節點往下探索概念，適合找 binary tree 深度
- Postorder traversal (左右中)
  - 隱含找當前節點的 parent 向上延伸概念，適合找 binary tree 高度
Breadth-first traversl: (level-order-traversal)
- 逐層遍歷

Recursive Steps

確定遞迴涵式的參數與返回值
- 確立在過程中哪些參數是需要做運算或是儲存等動作
- 確立每個遞迴要返回的值，從而確定返回的型態
確定終止條件
- 確立終止遞迴的方法，保存單層內容並返回上一層，慎防 stack overflow
確定單層遞迴的邏輯
- 確立在每一層需要處理的邏輯，會重複在每一層中使用到

Base Questions

Depth-first traversal

144. Binary Tree Preorder Traversal

Recursive
在單層遞迴邏輯中，依照順序處理遍歷方式 (preorder : 中左右)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def preorderTraversal(root: Optional[TreeNode]) -> List[int]:

  # step 1 :確定參數與返回值
  def traversal(current: Optional[TreeNode], result: List[int]) -> None: 
    # step 2 :確立終止條件
    if current == None: return 
    # step 3 :每層要處理的事項
    result.append(current.val) # 中
    taversal(current.left, result) # 左
    taversal(current.right, result) # 右

  result = []
  traversal(root, result)
  return result

Iterative
使用 Stack 儲存遍歷的次序
儲存順序為先右再左節點，取出時才會是正確的遍歷順序 (左->右)
使用空節點標記下一個要遍歷的節點 : 標記法 (適用所有排序)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
def preorderTraversal(root: Optional[TreeNode]) -> List[int]:
  if root is None: return []

  stack, result = [], []
  stack.append(root)
  while stack:
    node = stack[-1]
    if node:
      stack.pop()
      # 可以由下往上確認遍歷順序，中序：中左右 
      if node.right: stack.append(node.right) # 右 
      if node.left: stack.append(node.left) # 左
      stack.append(node) # 中
      # 加入空節點，用來辨識下一個要放進去遍歷結果的節點
      stack.append(None) 
    else:
      stack.pop() # 先行彈出空節點，下一個即是目標節點
      node = stack.pop() # 彈出目標節點
      result.append(node.val) # 執行單層所需操作
  return result

Related
- 145. Binary Tree Postorder Traversal
- 94. Binary Tree Inorder Traversal

Breadth-first traversl

102. Binary Tree Level Order Traversal

Recursive
隱含 preorder的遍歷順序，用來構建出整個樹的結構

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def levelOrder(root: Optional[TreeNode]) -> List[List[int]]:

  # step 1 :確定參數與返回值
  def order(current: Optional[TreeNode], result: List[int], depth: int) -> None: 
    # step 2 :確立終止條件
    if current == None: return 
    # step 3 :每層要處理的事項
    if len(result) == depth:
      result.append([])
    result[depth].append(current.val) # 中
    order(current.left, result, depth + 1) # 左 (backtracking)
    order(current.right, result, depth + 1) # 右 (backtracking)

  result = []
  order(root, result, 0)
  return result

Iterative
隱含 preorder的遍歷順序，用來構建出整個樹的結構
使用 Queue 儲存遍歷的次序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
from collections import deque
def levelOrder(root: Optional[TreeNode]) -> List[List[int]]:
  if root is None: return []
  result = []

  que = deque()
  que.append(root)
  while que:
    size = len(que) # que 長度會動態增減，要先固定初始大小
    temp = []
    for _ in range(size):
      node = que.popleft()
      temp.append(node.val) # 中
      if node.left: que.append(node.left) # 左
      if node.right: que.append(node.right) # 右
    result.append(temp)

  return result

Depth of Binary Tree

111. Minimum Depth of Binary Tree

postorder traversal : root -> leaf 最小距離 = 最小深度
Recursive
1. 參數與返回值
  - 參數：root，計算底下子樹最小深度
  - 返回值：深度
2. 終止條件
  - 若節點為空，回傳高度為 0
3. 單層邏輯
  - 若左子樹為空，右子樹不為空：最小深度為 1 + 右子樹深度
  - 若左子樹不為空，右子樹為空：最小深度為 1 + 左子樹深度
  - 若左右子樹皆不為空：最小深度為 1 + 左右子樹取最小值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def minDepth(root: Optional[TreeNode]) -> int:

  def getDepth(node: Optional[TreeNoed]) -> int:
    if node is None: return 0

    leftDepth = getDepth(node.left) # 左
    rightDepth = getDepth(node.right) # 右

    if node.left is None and node.right: return 1 + rightDepth
    if node.left and node.right is None: return 1 + leftDepth
    return 1 + min(leftDepth + rightDepth) # 中

  return getDepth(root)

levelorder traversal
Iterative
- 只有當左右節點皆為空時，遍歷才會是最低點 (其中一個節點不為空不算)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
from collections import deque
def minDepth(root: Optional[TreeNode]) -> int:
  if root in None: return  0

  depth = 0
  que = deque([root])
  while que:
    size = len(que)
    depth += 1
    for _ in range(size):
      node = que.popleft()
      if node.left: que.append(node.left) # 左
      if node.right: que.append(node.right) # 右
      if node.left is None and node.right is None: # 中
        return depth

Related
- 104. Maximum Depth of Binary Tree

Reference

代码随想录