94 二叉树的中序遍历

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

题解

有递归和非递归的两种解法

递归解法

递归解法很直接，所以直接上代码

var middleOrderRecursive = function(root) {
    const middleOrderInner = function(root, result) {
        if(!root) {
            return
        }
        middleOrderInner(root.left, result)
        result.push(root.val)
        middleOrderInner(root.right, result)
    }
    const result = []
    middleOrderInner(root, result)
    return result
}

非递归解法

我们需要一个指针来保存当前正在访问的节点, 同时我们需要一个栈来储存节点。 思路是首先定义一个current 节点以及stack栈，初始时节点指向root节点，然后判断current节点是否有左子树, 如果有左子树， 将左子树压入栈并且更新current信息，直到没有左子树为止。然后可以弹出，弹出后记录结果，并将current 指向右子树。

var middleOrderStack = function(root) {
    const result = []
    const stack = []
    if(!root) {
        return result
    }

    let current = root
    while(current || stack.length) {
        while(current) {
            //压入左子树
            stack.push(current)
            //更新current
            current = current.left
        }
        //弹出
        current = stack.pop()
        result.push(current.val)
        //现在应该访问右子树
        current = current.right
    }

    return result
}