[94] 二叉树的中序遍历 js

题目描述：给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

解题思路：

迭代法总结：

中序 左根右

一路向左，先所有左子树均入栈

1. 没有左节点的时候就出栈
2. 每弹出一个节点，都判断是否有右节点，有则入栈
3. 每一个入栈的节点都要判断是否有左节点，有则入栈

解法一（递归）：

const inOrder = (root) => {
  const traverse = (curNode,res) => {
    if(curNode === null) {
      return;
    }
    traverse(curNode.left,res);
    res.push(curNode.value);
    traverse(curNode.right,res);
  }
  let res = [];
  traverse(root);
  return res;
}

用时：

Your runtime beats 49.62 % of typescript submissions

// Your memory usage beats 65.13 % of typescript submissions (42.5 MB)

解法二（迭代（栈）第一次尝试）：

const inOrder = (root) => {
  if (root === null) {
        return [];
    }
    let stack = [root];
    let cur = root;
    let res = [];
    while (cur.left) {
      stack.push(cur.left);
      cur = cur.left;
    }
    
    while (stack.length) {
      // 没有左节点的时候出栈
        let popOne = stack.pop();
        res.push(popOne.val);
      // 每一个出栈的节点都要判断是否有右节点并入栈
        if (popOne.right) {
            stack.push(popOne.right);
          // 每一个入栈的节点都要判断是否有左节点
            let leftNode = popOne.right;
            while (leftNode.left) {
                stack.push(leftNode.left);
                leftNode = leftNode.left;
            }
        }
    }
    return res; 
}

用时：

// Your runtime beats 81.76 % of typescript submissions

// Your memory usage beats 20.97 % of typescript submissions (51.6 MB)

解法二（迭代（栈）简介答案）：

const inOrder = (root) => {
  if (root === null) {
      return [];
  }
  let stack = [];
  let cur = root;
  let res = [];
  
  while (stack.length || cur !== null) {
      if (cur === null) {
          // 左节点为空的时候就出栈
          cur = stack.pop();
          res.push(cur.val);
          // 右节点入栈
          cur = cur.right;
      } else {
          // 左节点有则左节点全部入栈
          stack.push(cur);
          cur = cur.left;
      }
  }
  return res;
}

用时：

// Your runtime beats 65.09 % of typescript submissions

// Your memory usage beats 16.6 % of typescript submissions (51.6 MB)