linye's Blog

全端工程師心得分享

0%

[LeetCode]144. Binary Tree Preorder 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: [1,2,3]

Example 2:

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

Example 3:

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

筆記

這題要練習樹的前序走訪，很簡單，就用深度優先走訪就完事了。

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

Recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function preorderTraversal(root: TreeNode | null, vals: number[] = []): number[] {
  // catch exception
  if (!root) return [];

  // push val to anwsers arr.
  vals.push(root!.val);

  // recursion traversal of tree.
  if (root?.left) preorderTraversal(root.left,vals);
  if (root?.right) preorderTraversal(root.right,vals);

  return vals;
};

iterative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function preorderTraversal(root: TreeNode | null): number[] {
  // catch exception
  if (!root) return [];

  // create anwsers arr and push the head val of the tree.
  let vals:number[] = [root?.val];
  // create pre go node list.
  let nodelist : TreeNode[] = [];
  
  // push 1st pre go node to list.
  if (root?.right) nodelist.push(root.right);
  if (root?.left) nodelist.push(root.left);

  // Iteration traversal of tree till there is no node in pre go list.
  while ( nodelist.length > 0) {
    const node = nodelist.pop()!;
    // push val into anwsers arr.
    if (node.val) vals.push(node?.val);
    if (node.right) nodelist.push(node.right);
    if (node.left) nodelist.push(node.left);
  }

  return vals;
};

成績

Language Runtime Beats Memory Usage Beats
TS iterative 83 ms 75.94% 44.8 MB 28.95%
TS recursive 107 ms 45.11% 44.5 MB 48.12%

score-image

迴圈寫法很輕鬆地就得到了高分，側面驗證了遞迴的確會影響效率(最佳化的例外)。