[Swift]LeetCode104.二叉树的最大深度|MaximumDepthofBinaryTree

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/9701156.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

return its depth = 3.

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

返回它的最大深度 3 。

32ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func maxDepth(_ root: TreeNode?) -> Int {
16         //将树分为左子树和右子树两部分，左右子树中深度最大的即为该树结构的深度。
17         var max:Int = 0
18         if root != nil
19         {
20             max += 1
21             var maxLeft:Int = maxDepth(root!.left)
22             var maxRight:Int = maxDepth(root!.right)
23             max += (maxLeft > maxRight ? maxLeft : maxRight)
24         }
25         return max   
26     }
27 }

24ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     
16     func maxDepth(_ root: TreeNode?) -> Int {
17         
18         guard let node = root else {
19             return 0
20         }
21         
22         return 1 + max(maxDepth(node.left), maxDepth(node.right))
23         
24     }
25 }

28ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     
16     func maxDepth(_ root: TreeNode?) -> Int {
17         
18         guard let node = root else {
19             return 0
20         }
21         
22         var depth: Int = 0
23         var stack: [TreeNode] = [node]
24         
25         while !stack.isEmpty {
26             
27             var currentStackSize = stack.count
28             
29             while currentStackSize > 0 {
30                 
31                 let lastNode = stack.popLast()!
32                 
33                 if let last = lastNode.left {
34                     stack.insert(last, at: 0)
35                 }
36                 
37                 if let right = lastNode.right {
38                     stack.insert(right, at: 0)
39                 }
40                 
41                 currentStackSize -= 1
42             }
43             
44             depth += 1
45         }
46         
47         return depth
48     }
49 }