LeetCode Js-144. Binary Tree Preorder Traversal

    AllenLi
    LeetCode Js-Binary TreeLeetCode Js-DFS/BFS

    Given the root of a binary tree, return the preorder traversal of its nodes’ values.

    給定二元樹的根，回傳對應節點的前序遍歷結果。

    Example 1:

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

    Example 2:

    Input: root = []
Output: []

    Example 3:

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

    solution:
    1. 首先，我們要知道 Preorder traversal(前序遍歷)所指的方向，接著:
    2. 我們在 preorderTraversal(root) 的函式中接受 binary tree 的輸入，並透過 dfs 來完成前序遍歷的結果。
    3. 在 dfs(node, result) 中，我們先判斷 node 是否為 null，如果是則直接返回。
    4. 如果 node 不是 null，代表該節點有值，我們開始做前序遍歷：
    4-1. result.push(node.val): 將當前節點的值加入到 result 陣列中。
    4-2. dfs(node.left, result): 使用遞迴對左子樹進行前序遍歷，持續走到左子樹最底層。
    4-3. dfs(node.right, result): 使用遞迴對右子樹進行前序遍歷。
    5. 這種遍歷方式首先訪問當前節點，然後遍歷左子樹，最後遍歷右子樹。這一切都是遞迴的方式來完成。

    ex.
中序遍歷步驟：
1. 訪問當前節點
2. 遍歷左子樹(直至最底層)
3. 遍歷右子樹

附上示意圖: https://ithelp.ithome.com.tw/articles/10289291

    Inorder Traversal

    Code 1: DFS

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

var preorderTraversal = function(root) {
   let result = [];
  dfs(root, result);
  return result;
}

function dfs(node, result) {
  if (!node) return;
  result.push(node.val);
  dfs(node.left, result);
  dfs(node.right, result);
}

//如自行在 replit 的 repo 上測試時，需額外進行 arrayToTreeNode 的轉換，代碼如下：
function arrayToTreeNode(arr) {
  if (!arr.length) return null;

  const root = new TreeNode(arr[0]);
  const queue = [root];
  let i = 1;

  while (queue.length && i < arr.length) {
    const current = queue.shift();
    ['left', 'right'].forEach((direction) => {
      if (i < arr.length && arr[i] !== null) {
        current[direction] = new TreeNode(arr[i]);
        queue.push(current[direction]);
      }
      i++;
    });
  }

  return root;
}

    FlowChart:
    Example 1

    const rootNode = new TreeNode(
  1,
  null,
  new TreeNode(
    2,
    new TreeNode(3),
    null,
  )
);

const rootNode = new TreeNode(
  1,
  new TreeNode(2)
  new TreeNode(3)
);

    Example 2

    const rootNode = []

    Example 3

    TreeNode { val: 1, left: null, right: null }

    Code 2: DFS

    Related Posts