# 广度遍历

遍历顺序:

img3

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

function breadthTraversal (tree) {
    let list = []
    let breadthTraversalFn = function (node) {
        if (node) {
            var stack = [node]
            while(stack.length !== 0) {
                node = stack.shift() // 从栈底取出
                list.push(node.value) // 添加当前节点的值至数组
                if (node.left) stack.push(node.left) // 将左子树推入栈中
                if (node.right) stack.push(node.right)
            }
        }
    }
    breadthTraversalFn(tree)
    return list
}

广度遍历是从二叉树的根结点开始,自上而下逐层遍历;在同一层中,按照从左到右的顺序对结点逐一访问。

阅读全文