二叉树遍历的统一写法

在二叉树前序遍历, 二叉树中序遍历以及二叉树的后序遍历中介绍了遍历二叉树的递归和非递归方法，但是前序遍历和中序遍历的非递归写法很不一样。导致了记忆起来比较费劲，有没有一种写法能够统一起来呢。

下面就介绍一种写法，只要换代码顺序就能够写出前序，中序和后序遍历。此方法参考了代码随想录的分析。

在非递归写法中，我们需要同时关注栈的维护 和 结果的维护，我们可以将要处理的节点做标记来告诉结果集来处理。详细可以看代码随想录的网站

中序遍历的非递归统一写法。关键点在于把要处理的节点后面加null

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

    stack.push(root)

    while(stack.length) {
        //先弹出栈
        const current = stack.pop()
        if (current) {
            // 先入右节点
            if(current.right) {
                stack.push(current.right)
            }
            //要处理中间节点，加入中间节点以及一个null
            stack.push(current)
            stack.push(null)
            //再入左节点
            if(current.left) {
                stack.push(current.left)
            }
        } else {
            //current 已经是null
            // 再次弹出，此时是处理节点
            const current = stack.pop()
            result.push(current.val)
        }
    }

    return result
}

前序遍历

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

    stack.push(root)

    while(stack.length) {
        //先弹出栈
        const current = stack.pop()
        if (current) {
            // 先入右节点
            if(current.right) {
                stack.push(current.right)
            }
            //再入左节点
            if(current.left) {
                stack.push(current.left)
            }
            //要处理中间节点，加入中间节点以及一个null
            stack.push(current)
            stack.push(null)
            
        } else {
            //current 已经是null
            // 再次弹出，此时是处理节点
            const current = stack.pop()
            result.push(current.val)
        }
    }

    return result
}

后序遍历

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

    stack.push(root)

    while(stack.length) {
        //先弹出栈
        const current = stack.pop()
        if (current) {
            //要处理中间节点，加入中间节点以及一个null
            stack.push(current)
            stack.push(null)
            // 先入右节点
            if(current.right) {
                stack.push(current.right)
            }
            //再入左节点
            if(current.left) {
                stack.push(current.left)
            }
        } else {
            //current 已经是null
            // 再次弹出，此时是处理节点
            const current = stack.pop()
            result.push(current.val)
        }
    }

    return result
}