linye's Blog

全端工程師心得分享

0%

[LeetCode]145. Binary Tree Postorder Traversal

發表於 分類於 ，

Algorithm I 筆記撰寫計畫 第十天第三題，共三題。

後續遍歷一個二元樹，然後把結果回傳。

點我開啟限制與範例

限制:

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

Example 1:

example-image-1

1
2
Input: root = [1,null,2,3]
Output: [3,2,1]

Example 2:

1
2
Input: root = []
Output: []

Example 3:

1
2
Input: root = [1]
Output: [1]

筆記

這題要練習樹的後序走訪，遵照以下步驟：

  1. 先拿左節點
  2. 再拿右節點
  3. 最後拿父節點

題目有要求要用迴圈的作法，所以遞迴跟迴圈各寫一個解答。

Recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
function postorderTraversal(root: TreeNode | null, res: number[] = []): number[] {
  // 有值就往內走
  if (root) {
    // 左邊有值就往左邊走
    postorderTraversal(root.left, res);
    // 右邊有值就往右邊走
    postorderTraversal(root.right, res);
    // 左右都走完了，塞回去
    res.push(root.val);
  }
  return res;
};

iterative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function postorderTraversal(root: TreeNode | null): number[] {
  // 例外處理
  if (!root) return [];
  // 答案陣列
  let result: number[] = [];
  // 待處理的節點
  let stack: TreeNode[] = [root];

  // 只要 stack 裡還有節點，就繼續跑
  while(stack.length > 0) {
    // 把最後一個節點拿出來
    let node = stack.pop()!;
    // 把這個節點的值放進答案陣列的最前面
    result.unshift(node.val);
    // 如果他有左右，就放進 stack 裡等待處理
    if (node.left) stack.push(node.left);
    if (node.right) stack.push(node.right);
  }
  return result;
};

成績

Language Runtime Beats Memory Usage Beats
TS iterative 91 ms 74.63% 44.7 MB 18.41%
TS recursive 80 ms 82.21% 43.9 MB 87.98%

score-image