輸入一棵二叉樹，求該樹的深度，從根結點到葉結點依次經過的結點（含根、葉結點）形成樹的一條路徑，最長路徑的長度為樹的深度
解題思路
遞回寫法，比較簡單
public class Solution {
public int TreeDepth(TreeNode root) {
if(root == null) {
return 0;
}
int left = TreeDepth(root.left);
int right = TreeDepth(root.right);
return Math.max(left, right) + 1;
}
}
非遞回寫法
depth 是當前結點所在的層數，count 是已經遍歷過的結點數，nextCount 是下層的結點總數，當 count == nextCount 的時候，代表本層的節點已經遍歷完畢
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
public int TreeDepth(TreeNode root) {
if(root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int depth = 0, count = 0, nextCount = 1;
while(queue.size() != 0) {
TreeNode top = queue.poll();
count++;
if(top.left != null) {
queue.add(top.left);
}
if(top.right != null) {
queue.add(top.right);
}
if(count == nextCount) {
nextCount = queue.size();
count = 0;
depth++;
}
}
return depth;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/184381.html
標籤：其他