JZ55 二叉樹的深度
描述
輸入一棵二叉樹，求該樹的深度，從根結點到葉結點依次經過的結點（含根、葉結點）形成樹的一條路徑，最長路徑的長度為樹的深度，根節點的深度視為 1 ，
方法1 遞回
思路：
最大深度是所有葉子節點的深度的最大值，深度是指樹的根節點到任一葉子節點路徑上節點的數量，因此從根節點每次往下一層深度就會加1，因此二叉樹的深度就等于根節點這個1層加上左子樹和右子樹深度的最大值，而每個子樹我們都可以看成一個根節點，繼續用上述方法求的深度，于是我們可以對這個問題劃為子問題，利用遞回來解決：
終止條件： 當進入葉子節點后，再進入子節點，即為空，沒有深度可言，回傳0.
回傳值： 每一級按照上述公式，回傳兩邊子樹深度的最大值加上本級的深度，即加1.
代碼
if(root == null) {
return 0;
} else {
return Math.max(TreeDepth(root.left), TreeDepth(root.right)) +1;
}
方法2 層次遍歷
思路
必須是一層一層的，那一層就是一個深度，有的層可能會很多節點，有的層如根節點或者最遠的葉子節點，只有一個節點，但是不管多少個節點，它們都是一層，因此我們可以使用層次遍歷，二叉樹的層次遍歷就是從上到下按層遍歷，每層從左到右，我們只要每層統計層數即是深度，
代碼
package esay.JZ55二叉樹的深度;
import java.util.LinkedList;
import java.util.Queue;
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public class Solution {
public int TreeDepth(TreeNode root) {
//方法1
/*if(root == null) {
return 0;
} else {
return Math.max(TreeDepth(root.left), TreeDepth(root.right)) +1;
}*/
if (root == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int res = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
res++;
}
return res;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/531803.html
標籤：其他
上一篇：硬核剖析Java鎖底層AQS原始碼，深入理解底層架構設計
下一篇：狂神說Go語言筆記—Go基礎語法