我的LeetCode：https://leetcode cn.com/u/ituring/ 我的LeetCode刷題源碼[GitHub]：https://github.com/izhoujie/Algorithmcii LeetCode 104. 二叉樹的最大深度 題目 給定一個二叉樹，找出其最大深 ...
我的LeetCode：https://leetcode-cn.com/u/ituring/
我的LeetCode刷題源碼[GitHub]：https://github.com/izhoujie/Algorithmcii
LeetCode 104. 二叉樹的最大深度
題目
給定一個二叉樹，找出其最大深度。
二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。
說明: 葉子節點是指沒有子節點的節點。
示例：
給定二叉樹 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree
著作權歸領扣網路所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。
解題思路
思路1-遞歸計算最深的子樹
思路解析：因為樹的深度是以最底層的葉子節點計算的，所以遞歸計算左右子樹，若不是葉子節點就將深度+1並遞歸處理，由於左右子樹都在遞歸，所以要求兩者的最大值；
步驟：
- 左右子樹遞歸，遞歸時，遇到非葉子節點就將深度+1並遞歸下層節點；
- 最終返回左右子樹深度值較大的即為樹的最大深；
演算法複雜度:
- 時間複雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
- 空間複雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
演算法源碼示例
package leetcode;
/**
* @author ZhouJie
* @date 2020年1月11日 下午8:25:09
* @Description: 104. 二叉樹的最大深度
*
*/
public class LeetCode_0104 {
}
// Definition for a binary tree node.
class TreeNode_0104 {
int val;
TreeNode_0104 left;
TreeNode_0104 right;
TreeNode_0104(int x) {
val = x;
}
}
class Solution_0104 {
/**
* @author: ZhouJie
* @date: 2020年5月22日 下午9:13:14
* @param: @param root
* @param: @return
* @return: int
* @Description: 1-遞歸計算；
*
*/
public int maxDepth(TreeNode_0104 root) {
return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
