Tree Traversal

如果你對於樹狀結構還不熟，推薦先了解 Tree。

Tree Traversal 指的是 「不重複地拜訪樹狀結構中所有節點」 的過程。

需要透過特定的順序，將樹裡面的每個節點都瀏覽過一遍（例如：列印節點、尋找特定值、或計算總和）。

主要分為兩大思維方向：

廣度優先搜尋（BFS, Breadth-First Search）：一層一層地看，把同一層的節點全部看完，再進入下一層。
深度優先搜尋（DFS, Depth-First Search）：沿著一條路徑一直往下鑽到最深處，碰到死胡同再折返回來走下一條。

白話理解

BFS 像是家族聚會時「一輩一輩」拍大合照：先讓最長輩那一輩全部入鏡，再換下一輩，一層一層來。DFS 則像是沿著一條家族血脈一路往下追到最年輕的後代，才回頭去追另一條血脈，一條線走到底才換下一條。

Breadth First Search (BFS)

從 Root 開始，由上到下、由左到右，一層一層地拜訪，有些人也會把這種搜尋方式稱為 Level-order Traversal。

適合用來尋找最短路徑，例如在社交網路中找出你和某個人的最短朋友關係鏈。

Tree
         10
      6     15
    3  8      20

BFS 遍歷結果 [10, 6, 15, 3, 8, 20]

Python
JavaScript
Java

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class Tree:
    def __init__(self):
        self.root = None

    # 關注在 BFS，忽略其餘 method

    def bfs(self):
        if not self.root:
            return []

        queue = [self.root]  # 儲存要造訪的 node
        visited = []         # 儲放已經造訪過的 node 值

        while queue:
            next_queue = []  # 儲存下一層要造訪的 node
                              # 也可以只用一個單一 Queue 實作，不定義 next_queue
                              # 一邊從前面取出（popleft）、一邊往後面塞入（append）。
            for node in queue:
                visited.append(node.val)
                if node.left:
                    next_queue.append(node.left)
                if node.right:
                    next_queue.append(node.right)
            queue = next_queue  # 指向下一層
        return visited

class Node {
  constructor(val) {
    this.val = val;
	this.left = null;
	this.right = null;
  }
}

class Tree {
  constructor() {
  	this.root = null;
  }
  
  // 關注在 BFS，忽略其餘 method

  BFS() {
    if (!this.root) return [];

    let queue = [this.root]     // 儲存要造訪的 node
    const visited = []          // 儲放已經造訪過的 node 值

    while (queue.length > 0) {
      const next_queue = []     // 儲存下一層要造訪的 node
                                // 也可以只用一個單一 Queue 實作，不定義 next_queue
                                // 一邊從前面取出（shift）、一邊往後面塞入（push）。
      for (let node of queue) {
        visited.push(node.val);
        node.left && next_queue.push(node.left);
        node.right && next_queue.push(node.right);
      }
      queue = next_queue        // 指向下一層
    }
    return visited;
  }
}

import java.util.ArrayList;
import java.util.List;

class Node {
    int val;
    Node left;
    Node right;

    Node(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class Tree {
    Node root;

    Tree() {
        this.root = null;
    }

    // 關注在 BFS，忽略其餘 method

    List<Integer> bfs() {
        List<Integer> visited = new ArrayList<>(); // 儲放已經造訪過的 node 值
        if (root == null) return visited;

        List<Node> queue = new ArrayList<>(); // 儲存要造訪的 node
        queue.add(root);

        while (!queue.isEmpty()) {
            List<Node> nextQueue = new ArrayList<>(); // 儲存下一層要造訪的 node
                                                       // 也可以只用一個單一 Queue 實作，不定義 nextQueue
                                                       // 一邊從前面取出（remove(0)）、一邊往後面塞入（add）。
            for (Node node : queue) {
                visited.add(node.val);
                if (node.left != null) nextQueue.add(node.left);
                if (node.right != null) nextQueue.add(node.right);
            }
            queue = nextQueue; // 指向下一層
        }
        return visited;
    }
}

Depth First Search (DFS)

分為三種：

PreOrder
PostOrder
InOrder

以下用 recursion 實作，但也可以用 stack 實作。

PreOrder

先處理當前節點，再遞迴走訪左子樹，最後遞迴走訪右子樹。

適合用來複製一棵樹，或是用來序列化（Serialize）樹狀結構，因為 Root 永遠在最前面。

         10
      6     15
    3  8      20

PreOrder 結果 [10, 6, 3, 8, 15, 20]

Python
JavaScript
Java

class Tree:
    def __init__(self):
        self.root = None

    # ...

    def dfs_pre_order(self):
        visited = []

        def helper(node):
            visited.append(node.val)  # 造訪 Node 時就先把 value 存起來
            if node.left:
                helper(node.left)
            if node.right:
                helper(node.right)

        if self.root:
            helper(self.root)
        return visited

class Tree {
  constructor() {
  	this.root = null;
  }
  
  ...

  DFSPreOrder() {
    const visited = [];
    function helper(node) {
      visited.push(node.val);       // 造訪 Node 時就先把 value 存起來
      node.left && helper(node.left);
      node.right && helper(node.right);
    }
    this.root && helper(this.root);
    return visited;
  }
}

import java.util.ArrayList;
import java.util.List;

class Tree {
    Node root;

    Tree() {
        this.root = null;
    }

    // ...

    List<Integer> dfsPreOrder() {
        List<Integer> visited = new ArrayList<>();
        if (root != null) helper(root, visited);
        return visited;
    }

    private void helper(Node node, List<Integer> visited) {
        visited.add(node.val);       // 造訪 Node 時就先把 value 存起來
        if (node.left != null) helper(node.left, visited);
        if (node.right != null) helper(node.right, visited);
    }
}

PostOrder

先遞迴走訪左子樹，再遞迴走訪右子樹，最後才處理當前節點。

適合用來刪除整棵樹，或是計算資料夾的大小（必須先知道所有子資料夾的大小，才能加總出父資料夾的大小）。

         10
      6     15
    3  8      20

PostOrder 結果 [3, 8, 6, 20, 15, 10]

Python
JavaScript
Java

class Tree:
    def __init__(self):
        self.root = None

    # ...

    def dfs_post_order(self):
        visited = []

        def helper(node):
            if node.left:
                helper(node.left)
            if node.right:
                helper(node.right)
            visited.append(node.val)  # 造訪 Node 的最後才存 value

        if self.root:
            helper(self.root)
        return visited

class Tree {
  constructor() {
  	this.root = null;
  }
  
  ...

  DFSPostOrder() {
    const visited = [];
    function helper(node) {
      node.left && helper(node.left);
      node.right && helper(node.right);
      visited.push(node.val);   // 造訪 Node 的最後才存 value
    }
    this.root && helper(this.root);
    return visited;
  }
}

import java.util.ArrayList;
import java.util.List;

class Tree {
    Node root;

    Tree() {
        this.root = null;
    }

    // ...

    List<Integer> dfsPostOrder() {
        List<Integer> visited = new ArrayList<>();
        if (root != null) helper(root, visited);
        return visited;
    }

    private void helper(Node node, List<Integer> visited) {
        if (node.left != null) helper(node.left, visited);
        if (node.right != null) helper(node.right, visited);
        visited.add(node.val);   // 造訪 Node 的最後才存 value
    }
}

InOrder

先遞迴走訪左子樹，再處理當前節點，最後遞迴走訪右子樹。

在 Binary Search Tree 中，InOrder 的輸出結果一定會是由小到大排序好的陣列！

         10
      6     15
    3  8      20

InOrder 結果 [3, 6, 8, 10, 15, 20]

Python
JavaScript
Java

class Tree:
    def __init__(self):
        self.root = None

    # ...

    def dfs_in_order(self):
        visited = []

        def helper(node):
            if node.left:
                helper(node.left)
            visited.append(node.val)  # 造訪完 Left child 後再將 Node value 存起來
            if node.right:
                helper(node.right)

        if self.root:
            helper(self.root)
        return visited

class Tree {
  constructor() {
  	this.root = null;
  }
  
  ...

  DFSInOrder() {
    const visited = [];
    function helper(node) {
      node.left && helper(node.left);
      visited.push(node.val);       // 造訪完 Left child 後再將 Node value 存起來
      node.right && helper(node.right);
    }
    this.root && helper(this.root);
    return visited;
  }
}

import java.util.ArrayList;
import java.util.List;

class Tree {
    Node root;

    Tree() {
        this.root = null;
    }

    // ...

    List<Integer> dfsInOrder() {
        List<Integer> visited = new ArrayList<>();
        if (root != null) helper(root, visited);
        return visited;
    }

    private void helper(Node node, List<Integer> visited) {
        if (node.left != null) helper(node.left, visited);
        visited.add(node.val);       // 造訪完 Left child 後再將 Node value 存起來
        if (node.right != null) helper(node.right, visited);
    }
}

複雜度

時間複雜度：無論是 DFS 還是 BFS，所有的 Node 都剛好被拜訪一次，因此時間複雜度皆為 O(N)（N 為節點總數）。
空間複雜度：
- DFS
  - 取決於樹的高度（也就是 Recursion Call Stack 的深度）。
  - 最壞情況（樹長成一條直線）是 O(N)，最好情況（完全平衡樹）是 $O(log N)$。
- BFS
  - 取決於樹中「最寬的那一層」有多少節點（Queue 裡面最多會裝那一層的所有節點）。
  - 在完全二元樹中，最底層約佔總節點的一半，因此最壞情況空間複雜度為 O(N)。

適用情況

BFS（Level-order）：適合尋找最短路徑，例如社交網路中找出兩人之間最短的朋友關係鏈。
PreOrder：適合複製一棵樹，或是序列化（Serialize）樹狀結構，因為 Root 永遠在最前面。
PostOrder：適合刪除整棵樹，或是計算資料夾大小這類「必須先算完所有子節點，才能算自己」的問題。
InOrder：在 Binary Search Tree 中，InOrder 的輸出結果一定是由小到大排序好的陣列，適合需要「依序取值」的情境。

常見誤區

PreOrder / InOrder / PostOrder 傻傻分不清楚：三者的差別只在於「處理當前節點的時機點」，可以死記口訣：PreOrder 是先（Pre）處理自己再看左右；InOrder 是處理完左邊、中間（In the middle）處理自己、再看右邊；PostOrder 是最後（Post）才輪到處理自己。
忘記 InOrder 對 BST 才有「由小到大排序」的特性：這個特性只在 Binary Search Tree 才成立，一般的 Binary Tree 用 InOrder 走訪，結果並不會是排序好的。
DFS 遞迴忘記處理空節點（null）：走訪時如果沒有先判斷 node.left / node.right 是否存在就直接遞迴呼叫，會因為對 null 呼叫方法而出錯，寫法上習慣用 node.left && helper(node.left) 這種寫法可以省去額外的 if 判斷。

Breadth First Search (BFS)​

Depth First Search (DFS)​

PreOrder​

PostOrder​

InOrder​

複雜度​

適用情況​

常見誤區​