[Swift]LeetCode104. 二叉树的最大深度 | Maximum Depth of Binary Tree

时间:2021-12-15 17:28:32

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],

    3
   / \
  9  20
    /  \
   15   7

return its depth = 3.

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

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

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

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

    3
   / \
  9  20
    /  \
   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 }