Online Judge►LeetCode

[LeetCode] 94 - Binary Tree Inorder Traversal

題意

使用非遞迴的方式 Inorder Traversal 二元樹。

解法

Inorder 順序是左子樹、根、右子樹，利用 stack 來完成 Traversal 。

往左子樹下看並同時將一路上的根放入 stack，當碰到 null 時代表該節點左子樹已到底，pop 出該節點（此時視為根）且紀錄，因此接著進入該節點右子樹重複步驟上述步驟，直到該節點右子樹遍歷完，代表該節點的根之左子樹遍歷完畢，再依此類推。

程式

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
26
27
28
29
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
  if ( !root ) return [];
  
  let stack = [];
  let result = [];
  let node = root;
  
  while( stack.length !== 0 || node !== null ){
    while ( node !== null ){
      stack.push(node);
      node = node.left;
    }
    node = stack.pop();
    result.push(node.val);
    node = node.right;
  }
  return result;
};