劍指 Offer 55 - I. 二叉樹的深度
題目：
輸入一棵二叉樹的根節點，求該樹的深度，從根節點到葉節點依次經過的節點（含根、葉節點）形成樹的一條路徑，最長路徑的長度為樹的深度，
例如：
給定二叉樹 [3,9,20,null,null,15,7]，
回傳它的最大深度 3 ，
解題思路：
樹的后序遍歷往往利用遞回或堆疊實作，這里使用遞回，
1.先找到此樹的深度和其左（右）子樹的深度之間的關系，可以發現此樹的深度等于左子樹的深度與右子樹的深度中的最大值 +1 ，
2.當 root? 為空，說明已越過葉節點，因此回傳 深度 0，
3.計算節點 root?的左子樹的深度，即呼叫maxDepth(root.left)；計算節點root的右子樹的深度 ，即呼叫maxDepth(root.right)；
4.回傳 此樹的深度 ，即 max(maxDepth(root.left), maxDepth(root.right)) + 1
代碼如下：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
* 執行結果：通過
* 執行用時：0 ms, 在所有 Java 提交中擊敗了100.00%的用戶
* 記憶體消耗：38.2 MB, 在所有 Java 提交中擊敗了75.40%的用戶
* 通過測驗用例：39 / 39
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root == null){
return 0;
}
return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/345650.html
標籤：其他
下一篇：145. 二叉樹的后序遍歷