gogoend / blog

blogs, ideas, etc.
MIT License
9 stars 2 forks source link

N叉树的遍历 —— 深度优先、广度优先 #44

Open gogoend opened 4 years ago

gogoend commented 4 years ago

最近在做一个项目使用到了中国行政区划三级树状结构,我突然有种想法,想在树状结构每一层的每一项目,按照层级给一个level值,标识出该项目属于哪一层级。

我的想法是对每一层进行遍历,一层一层往下走。按照以往遍历树的方式,我可能会进行递归。但无奈发现,事情好像不是这么简单 —— 递归操作是向树的下方进行的(深度优先),而我这里想做的加层级标识这个操作应当是在当前层次向右测进行,进行完成后进入下一层的(层序优先)。

后面各种百度,最终在LeetCode上找到了答案。

参见

429. N叉树的层序遍历 剑指 Offer 32 - I. 从上到下打印二叉树

gogoend commented 4 years ago

如图所示,这是一颗树: image 将其表示为JavaScript中的一个变量:

let aTree = {
    key: 0,
    children: [
        {
            key: 1,
            children: [
                {
                    key: 3,
                    children: [
                        {
                            key: 7,
                            children: null
                        },
                        {
                            key: 8,
                            children: null
                        }
                    ]
                },
                {
                    key: 4,
                    children: [
                        {
                            key: 9,
                            children:null
                        }
                    ]
                }
            ]
        },
        {
            key: 2,
            children: [
                {
                    key: 5,
                    children: null
                },
                {
                    key: 6,
                    children: [
                        {
                            key: 10,
                            children: null
                        },
                        {
                            key: 11,
                            children: null
                        }, {
                            key: 12,
                            children: null
                        }
                    ]
                }
            ]
        }
    ]
}

我们希望,在遍历过程中,树中的节点能够按照0、1、2、3、4、5、6、7、8、9、10、11、12的顺序输出,也就是先从左向右遍历,遍历完当前层次后进入下一层次,再次从右向右遍历…… 因此,这里就用到了层序遍历。

gogoend commented 4 years ago

在遍历过程中,我们需要用到一种数据结构 —— 队列。队列是一种先进先出(FIFO)的数据结构,遍历时我们需要把树中每一节点一个个从压入队列尾部,并按顺序从队列头部弹出。

image

遍历开始前,我们将根节点放入空队列中,这样队列里就有了一个元素。

接下来我们判断队列是否为空。如果队列为空,表明整个层序遍历过程已经结束了,可直接返回,否则就继续遍历。

我们初始化一个空数组levelArr,在进行遍历时,当前层级所有节点将会放入其中;同时使用一个变量len存下此时队列的长度。 接下来就对当前queue中当前层级的所有项目进行循环。若i小于len,就将队列中第一个元素(队头)弹出,并放入levelArr中;同时我们来看看刚刚弹出的元素下是否有孩子,若有孩子我们就把孩子压入queue尾部(如果这是第0层遍历的话,此处仅包含一个根节点,弹出后队列为空,此时第0层遍历完成);若i不再小于len,就表示这一层级的循环已经结束,这时queue里全是下一层级的元素,不再包含当前层级的元素。重复这一步操作,直到最后节点不再有孩子能够再压入队列中,此时整个层序遍历结束。

代码实现

function levelOrderTraverse(root){
    if(!root) return []
    let queue = [root]
    let resultArr=[]
    while(queue.length){
        let levelArr = []
        let len = queue.length
        for(let i=0;i<len;i++){
            let current = queue.shift()
            levelArr.push(current)
            if(current.children && current.children.length){
                queue.push(...current.children)
            }
        }
        resultArr.push(levelArr)
    }
    return resultArr
}