我的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;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/185238.html
標籤：Java