输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。(其中节点总数 <= 10000)
例子:
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
它的最大深度 3
解题思路:
深度优先搜索
主要通过递归来处理
关键点: 树的深度 等于 左子树的深度 与 右子树的深度 中的 最大值 +1 。
1
2
3
4
5
6
代码:
/**
* Definition for a binary tree node.
* public class TreeNode {
* public var val: Int
* public var left: TreeNode?
* public var right: TreeNode?
* public init(_ val: Int) {
* self.val = val
* self.left = nil
* self.right = nil
* }
* }
*/
class Solution {
func maxDepth(_ root: TreeNode?) -> Int {
if root != nil {
let maxleft = maxDepth(root!.left),
maxright = maxDepth(root!.right)
return max(maxleft, maxright) + 1
}
return 0
}
}
当然我们也可以简洁下代码, 二行即可
class Solution {
func maxDepth(_ root: TreeNode?) -> Int {
if root == nil { return 0 }
return max(maxDepth(root!.left), maxDepth(root!.right)) + 1
}
}
题目来源：力扣（LeetCode） 感谢力扣爸爸 :)
IOS 算法合集地址
网友评论