抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

28 | 面试题:二叉树层次遍历

102. 二叉树的层序遍历

解法一:BFS

直接遍历,直接存放,一层一层放完。

判断当前层已结束的两种方法:

  1. 将当前层数保存到队列中(不推荐)
  2. Beetch process(代码中体现)

时间复杂度:O(N)

fun levelOrder(root: TreeNode?): ArrayList<ArrayList<Int>> {
val res = ArrayList<ArrayList<Int>>()
root ?: return res

val q = LinkedList<TreeNode>()
q.add(root)

while (q.isNotEmpty()) {
val levelSize = q.size
val currentLevel = ArrayList<Int>()

for (i in 0 until levelSize) {
val curNode = q.poll()
currentLevel.add(curNode.`val`)
curNode.left?.also {
q.add(it)
}
curNode.right?.also {
q.add(it)
}
}
res.add(currentLevel)
}
return res
}

解法二:DFS 也可

深度遍历,按层填充,逐渐放完。

时间复杂度:O(N)

递归写法:

fun levelOrder(root: TreeNode?): ArrayList<ArrayList<Int>> {
val res = ArrayList<ArrayList<Int>>()
root ?: return res
dfs(root, res, 0)
return res
}

private fun dfs(node: TreeNode?, res: ArrayList<ArrayList<Int>>, level: Int) {
node ?: return
//预先建立坑位
if (res.size - 1 < level) {
res.add(ArrayList())
}
//直接使用坑位
res[level].add(node.`val`)

dfs(node.left, res, level + 1)
dfs(node.right, res, level + 1)
}

非递归写法:问了大佬,确实有解

class Solution {
    fun addNode(res: ArrayList<ArrayList<Int>>, node: Pair<TreeNode?, Int>) {
        if (res.size == 0 || node.second + 1 > res.size) {
            for (i in 0 until node.second + 1 - res.size) {
                res.add(ArrayList())
            }
        }
        res[node.second].add(node.first!!.`val`)
    }

    fun levelOrder(root: TreeNode?): ArrayList<ArrayList<Int>> {
        val res = ArrayList<ArrayList<Int>>()
        val stack = Stack<Pair<TreeNode?, Int>>()
        var cur = Pair(root, 0)
        while (cur.first!=null || stack.isNotEmpty()) {
            while (cur.first !=null) {
                addNode(res, cur)
                val node = cur.first
                stack.push(Pair(node!!.right, cur.second + 1))
                cur = Pair(node.left, cur.second + 1)
            }
            cur = stack.pop()
        }
        return res
    }

}

两种方法都还好,不好理解的话,配合断点调试食用。如果是图的遍历,需加上 visited 判断。

附上大佬的 C++原版,或许有人用得着:


0条评论

发表评论