題目

https://leetcode.com/problems/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.

解答

C#

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int MaxDepth(TreeNode root) {
        if (root == null)
            return 0;
        return Math.Max(MaxDepth(root.right), MaxDepth(root.left)) + 1;
    }
}

結果

Runtime: 92 ms, faster than 96.49% of C# online submissions.

Memory Usage: 24.7 MB, less than 5.88% of C# online submissions.

Time Complexity: O(n)

Space Complextiy: O(1)

為什麼我要這樣做？

還記得 tree 怎麼運用嗎？我們來回顧一下　↓
[Day 22] 演算法刷題 LeetCode 101. Symmetric Tree (Easy) Part 1 - Recursion
[Day 23] 演算法刷題 LeetCode 101. Symmetric Tree (Easy) Part 2 - Iteration

這題其實沒有很難，只是要找出這顆樹的最大深度，所以只要遞迴寫好就好，就看你熟不熟悉 遞迴 了！！

1. 判斷 root 是否為 null，若是則回傳 0
2. 回傳此節點的深度
   • 遞迴找出 root 的right 右節點 最大深度
   • 遞迴找出 root 的left 左節點 最大深度
   • 比較兩個節點的最大深度，使用Math.Max 取 最大值
   • 最後並 +1，代表需要往上多加這一層

以上就是這次 LeetCode 刷題的分享啦！
如果其它人有更棒的想法及意見，請留言或寄信(t4730@yahoo.com.tw) 給我。
那我們就下回見囉