中序遍历|博客系列 | 前端进阶之旅 - 前端求职面试刷题宝典

# 中序遍历

遍历顺序为：

遍历之后：["LL","L","LR","Root","RL","R","RR"]

递归遍历

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

@前端进阶之旅: 代码已经复制到剪贴板

非递归遍历

非遍历我是这样考虑的：

会先把中间"Root"压入栈中
然后开始压入"Root"的左边节点
当左边节点全部都压进栈了之后，["Root", "L", "LL"]
要开始从栈的末位取出value了，同时要开始把右边的也压入栈了
当取出"LL"的时候，"LL"已经没有左右子节点了，所以会继续从栈的末位取出value
也就是取出了"L"，"L"还是有右节点的，所以要把"LR"压入栈
"LR"压入栈之后，"LR"也是没有左子节点的，所以会从栈的末位取出，且它又没有右子节点，就会继续取出
继续取出"Root"，这时候再开始把node = "Root".right了，也就是要开始遍历"R"了
以此类推把"R"也按上面的步骤遍历完

function inOrderUnRec (tree) {
    let list = []
    let inOrderUnRecFn = function (node) {
        if (node) { // 当前节点存在
            let stack = [] // 定义一个空的栈
            while(stack.length !== 0 || node) { // 判断栈不为空或者当前节点存在
                if (node) { // 若是节点存在
                    stack.push(node) // 将当前节点推入栈
                    node = node.left // 将左子树作为当前节点
                } else { // 当前节点不存在(左子树为空)
                    node = stack.pop() // 从栈中取出节点
                    list.push(node.value)
                    node = node.right // 将右子树作为当前节点
                }
            }
        }
    }
    inOrderUnRecFn(tree)
    return list
}