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

伪斜杠青年

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

29 | 面试题:二叉树的最大和最小深度

104. 二叉树的最大深度

解法一:DFS递归

时间复杂度:O(N)

图解:来自leetcode 官方

/**
* Example:
* var ti = TreeNode(5)
* var v = ti.`val`
* Definition for a binary tree node.
* class TreeNode(var `val`: Int) {
* var left: TreeNode? = null
* var right: TreeNode? = null
* }
*/
class Solution {
fun maxDepth(root: TreeNode?): Int {
root ?: return 0
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
}
}

解法二:DFS非递归

保存一个值 max 用于记录level深度,每次遍历时遇到叶子节点与 max 值进行比较,大于 max 则更新 max即可。

时间复杂度:O(N)

class Solution {
fun maxDepth(root: TreeNode?): Int {
root ?: return 0
var max = Int.MIN_VALUE
val stack = Stack<Pair<TreeNode?, Int>>()
var cur = Pair<TreeNode?, Int>(root, 0)
while (cur.first != null || stack.isNotEmpty()) {
while (cur.first != null) {
if (cur.first!!.left == null && cur.first!!.right == null) {
max = Math.max(max, cur.second + 1)
}

val node = cur.first
stack.push(Pair(node!!.right, cur.second + 1))
cur = Pair(node.left, cur.second + 1)
}
cur = stack.pop()
}
return max
}
}

解法三:BFS

由于是按层扫描,最后一层就是最大深度。

时间复杂度:O(N)

class Solution {
fun maxDepth(root: TreeNode?): Int {
root ?: return 0

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

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

111. 二叉树的最小深度

解法一:DFS递归

需要注意的是特殊情况,没有左子树的时候与没有右子树的时候。

时间复杂度:O(N)

/**
* Example:
* var ti = TreeNode(5)
* var v = ti.`val`
* Definition for a binary tree node.
* class TreeNode(var `val`: Int) {
* var left: TreeNode? = null
* var right: TreeNode? = null
* }
*/
class Solution {
fun minDepth(root: TreeNode?): Int {
root ?: return 0
root.left ?: return 1 + minDepth(root.right)
root.right ?: return 1 + minDepth(root.left)

val minL = minDepth(root.left)
val minR = minDepth(root.right)

return Math.min(minL, minR) + 1
}
}

简化版本:主要是return 时增加了情况覆盖

class Solution {
fun minDepth(root: TreeNode?): Int {
root ?: return 0
val minL = minDepth(root.left)
val minR = minDepth(root.right)
return if (minL == 0 || minR == 0) {
minL + minR + 1
} else {
Math.min(minL, minR) + 1
}
}
}

解法二:DFS非递归

保存一个值 min 用于记录level深度,每次遍历时遇到叶子节点与 min 值进行比较,小于 min 则更新 min即可。

时间复杂度:O(N)

class Solution {
fun minDepth(root: TreeNode?): Int {
root ?: return 0
var min = Int.MAX_VALUE
val stack = Stack<Pair<TreeNode?, Int>>()
var cur = Pair<TreeNode?, Int>(root, 0)
while (cur.first != null || stack.isNotEmpty()) {
while (cur.first != null) {
if (cur.first!!.left == null && cur.first!!.right == null) {
min = Math.min(min, cur.second + 1)
}

val node = cur.first
stack.push(Pair(node!!.right, cur.second + 1))
cur = Pair(node.left, cur.second + 1)
}
cur = stack.pop()
}
return min
}
}

解法三:BFS

由于是按层扫描,那么扫描时判断是否是叶子节点即可。

时间复杂度:O(N)

class Solution {
fun minDepth(root: TreeNode?): Int {
root ?: return 0

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

while (q.isNotEmpty()) {
val levelSize = q.size
for (i in 0 until levelSize) {
val curNode = q.poll()
curNode.left?.also {
q.add(it)
}
curNode.right?.also {
q.add(it)
}

if (curNode.left == null && curNode.right == null) {
return ++level
}
}
level++
}
return level
}
}

0条评论

发表评论