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

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

/**
 * 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 {
        //将树分为左子树和右子树两部分，左右子树中深度最大的即为该树结构的深度。
        var max:Int = 0
        if root != nil
        {
            max += 1
            var maxLeft:Int = maxDepth(root!.left)
            var maxRight:Int = maxDepth(root!.right)
            max += (maxLeft > maxRight ? maxLeft : maxRight)
        }
        return max   
    }
}

---

 

24ms

/**
 * 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 {
        
        guard let node = root else {
            return 0
        }
        
        return 1 + max(maxDepth(node.left), maxDepth(node.right))
        
    }
}

---

28ms

/**
 * 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 {
        
        guard let node = root else {
            return 0
        }
        
        var depth: Int = 0
        var stack: [TreeNode] = [node]
        
        while !stack.isEmpty {
            
            var currentStackSize = stack.count
            
            while currentStackSize > 0 {
                
                let lastNode = stack.popLast()!
                
                if let last = lastNode.left {
                    stack.insert(last, at: 0)
                }
                
                if let right = lastNode.right {
                    stack.insert(right, at: 0)
                }
                
                currentStackSize -= 1
            }
            
            depth += 1
        }
        
        return depth
    }
}