94. Binary Tree Inorder Traversal

Leetcode

https://leetcode.com/problems/binary-tree-inorder-traversal/

題目

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]

解答

• 方法一

Recursion

var inorderTraversal = function(root) {
    if (root === null) return [];
    
    const result = [];
    const inorder = (node) => {
        if(node) {
            inorder(node.left);
            result.push(node.val);
            inorder(node.right);
        }
    }
    inorder(root);
    
    return result;
};

Runtime: 60 ms, faster than 95.03% of JavaScript online submissions for Binary Tree Inorder Traversal.

Memory Usage: 42.3 MB, less than 31.75% of JavaScript online submissions for Binary Tree Inorder Traversal.

• 方法二

Iteration

var inorderTraversal = function(root) {
    if (root === null) return [];
    
    const result = [];
    const stack = [];
    let curr = root;
    while (curr != null || stack.length) {
      // 一直往左邊找直到找到左子樹為 null
      while(curr != null) {
          stack.push(curr);
          curr = curr.left;
      }
      curr = stack.pop();
      result.push(curr.val);
      curr = curr.right;
    }
    
    return result;
};

Runtime: 96 ms, faster than 38.70% of JavaScript online submissions for Binary Tree Inorder Traversal.

Memory Usage: 42.1 MB, less than 44.91% of JavaScript online submissions for Binary Tree Inorder Traversal.

• 方法三

Morris method

var inorderTraversal = function(root) {
    if (root === null) return [];
    
    const result = [];
    let curr = root;
    let prev;
    while (curr != null) {
      if(curr.left === null) {
          result.push(curr.val);
          curr = curr.right;
      } else {
          prev = curr.left;
          // 找出左子樹最右邊的節點
          while(prev.right !== null) {
              prev = prev.right;
          }
          // 將 curr 接在左子樹最右邊節點的右邊
          prev.right = curr;
          const temp = curr;
          // 樹根改為左子樹
          curr = curr.left;
          // curr 在接完後，原本的左子樹要清空
          temp.left = null;
      }
    }
    
    return result;
};

Runtime: 73 ms, faster than 71.57% of JavaScript online submissions for Binary Tree Inorder Traversal.

Memory Usage: 42 MB, less than 44.91% of JavaScript online submissions for Binary Tree Inorder Traversal.

參考資料

https://www.cnblogs.com/anniekim/archive/2013/06/15/morristraversal.html