LeetCode Js-94. Binary Tree Inorder Traversal

    AllenLi
    LeetCode Js-Binary TreeLeetCode Js-DFS/BFS

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

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

    Example 1:

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

    Example 2:

    Input: root = []
Output: []

    Example 3:

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

    solution:
    1. 首先，我們要知道 Inorder traversal(中序遍歷)所指的方向，接著:
    2. 我們在 inorderTraversal(root) 的函式中接受 binary tree 的輸入，並透過 dfs來完成中序遍歷的結果。
    3. 在 dfs(node, result) 中，我們先判斷 node 是否為 null，如果是則直接返回。
    4. 如果 node 不是 null，代表該節點有值，我們開始做中序遍歷：
    4-1. dfs(node.left, result): 使用遞迴對左子樹進行中序遍歷。
    4-2. result.push(node.val): 將當前節點的值加入到 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 inorderTraversal = function(root) {
  let result = [];
  dfs(root, result);
  return result;
}

function dfs(node, result) {
  if (!node) return;

  dfs(node.left, result);
  result.push(node.val);
  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(3)
  new TreeNode(2)
);

    Example 2

    const rootNode = []

    Example 3

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

    Related Posts