輸入一棵二叉樹的根節(jié)點，求該樹的深度。從根節(jié)點到葉節(jié)點依次經(jīng)過的節(jié)點（含根、葉節(jié)點）形成樹的一條路徑，最長路徑的長度為樹的深度。(其中節(jié)點總數(shù) <= 10000)

例子:

給定二叉樹 [3,9,20,null,null,15,7]

      3
     /  \
    9   20
        / \
       15  7

它的最大深度 3

解題思路:

深度優(yōu)先搜索

主要通過遞歸來處理

關(guān)鍵點: 樹的深度 等于 左子樹的深度 與 右子樹的深度 中的 最大值 +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 算法合集地址