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;
};