94. 二叉树的中序遍历

题目描述

给定一个二叉树，返回它的中序 遍历。

示例:

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

输出: [1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

递归：

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

栈 + 标记：

/**
 * 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 res = [];
  // 先把root放栈里
  let stack = [root];
  // 直到栈处理完毕之前都做这个循环
  while (stack.length) {
    // 取出栈顶元素
    let node = stack.pop();
    // 看下是否是节点，如果是，按遍历反序推进栈里，因为这样出栈才是顺序
    if (node instanceof TreeNode) {
      stack.push(node.right);
      // 这里直接把值推进去，就可以区分是否子树
      stack.push(node.val);
      stack.push(node.left);
    // 看下如果是值的话，直接写进遍历结果中  
    } else if (typeof node === 'number') {
      res.push(node);
    }
  }
  return res;
};

栈：（时间跟上面的一样，但上面的容易理解很多）

var inorderTraversal = function(root) {
    const res = [];
    const stk = [];
    while (root || stk.length) {
        while (root) {
            stk.push(root);
            root = root.left;
        }
        root = stk.pop();
        res.push(root.val);
        root = root.right;
    }
    return res;
};