94. 二叉樹的中序周遊（JavaScript）（疊代法與遞歸法）

給定一個二叉樹，傳回它的中序 周遊。

示例:

輸入: [1,null,2,3]
   1
    \
     2
    /
   3

輸出: [1,3,2]
           

進階: 遞歸算法很簡單，你可以通過疊代算法完成嗎？

解法一：遞歸法

遞歸法不多說，按照左子樹、根節點、右子樹的順序進行周遊。

遞歸法也有兩種寫法，一種是遞歸函數本身，一種是在閉包中遞歸（即在函數中建立新函數，遞歸這個新函數）。

一、

注意的是數組的連接配接：arrayA = arrayA.concat(arrayB)          concat并不改變原數組。

/**
 * 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 array = [];
  if (root.left) {        // 左子樹不為空
    array = array.concat(inorderTraversal(root.left));
  }
  array.push(root.val);        //根節點
  if (root.right) {        // 右子樹不為空
    array = array.concat(inorderTraversal(root.right));
  }
  return array;
};
           

二、建立新函數，代碼更簡潔

/**
 * 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) {
  let values = [];
  const inorder = function(root) {
    if (!root) return;
    inorder(root.left);
    values.push(root.val);
    inorder(root.right);
  }
  inorder(root);
  return values;
};
           

解法二：疊代法

疊代法與遞歸不同，不調用函數本身，而是采用循環的方式周遊所有節點。既然循環，那必須用到棧或者隊列來不斷加入節點和移除節點，直到棧或隊列為空時結束疊代。

到底應該用棧還是隊列呢？我們知道若是層序周遊，是要用隊列的，每一層的兄弟節點入隊列可以保證出隊列時的先後順序不變。

但這裡的中序周遊，是一種深度搜尋，探索根節點的左子樹，左子樹的左子樹，左子樹的左子樹的左子樹……直到左子樹為空。這樣一種特點需要用到棧的先進後出的特點，将根節點的右子節點入棧，保證将左子樹的全部節點以及根節點周遊完再來拿出這個右子節點。

具體操作是：對于任一節點p，

1. 若其左孩子不為空，則将p入棧并将p的左孩子置為目前的p，然後對目前結點p再進行相同的處理；
2. 若其左孩子為空，則取棧頂元素并進行出棧操作，通路該棧頂結點，然後将棧頂結點的右孩子置為目前的p
3. 直到p為null且棧為空則結束周遊

/**
 * 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) {
  var stack = [],
      result = [],
      p = root;
  while (p || stack.length) {
    while (p) {
      stack.push(p);
      p = p.left;
    }
    p = stack.pop();
    result.push(p.val);
    p = p.right;
  }
  return result;
};