后序遍历|博客系列

function inOrderRec (tree) {
    let list = []
    let inOrderRecFn = function (node) {
        if (node) {
            if (node.left) inOrderRecFn(node.left)
            if (node.right) inOrderRecFn(node.right)
            list.push(node.value)
        }
    }
    inOrderRecFn(tree)
    return list
}

function postOrderUnRec (tree) {
    let list = []
    let postOrderUnRecFn = function (node) {
        if (node) { // 当前节点存在
            let stack = [node] // 将当前节点推入栈
            let tmp = null // 定义一个空的对象用于盛放上一次入栈、出栈的节点
            while(stack.length !== 0) { // 判断条件为 stack 不为空
                tmp = stack[stack.length - 1] // 保存住栈顶的值
                if (tmp.left && tmp.left !== node && tmp.right !== node) { // 若栈顶的值存在左子树且当前的节点不为左子树和右子树节点
                    stack.push(tmp.left) // 将左子树推入栈中
                } else if (tmp.right && tmp.right !== node) {
                    stack.push(tmp.right)
                } else { // 左子树和右子树都遍历完了之后
                    list.push(stack.pop().value)
                    node = tmp
                }
            }
        }
    }
    postOrderUnRecFn(tree)
    return list
}