題型解說
這是一題難度為簡單的題目
需要設計一個方法,此方法會傳入一個二元樹 root
回傳這棵樹最深的節點是第幾層
解題思路
這題基本上就是用遞迴去濾到最後深的一個節點,雖然說使用迴圈也可以做到
但就必須多寫一點程式碼,底下也會提供迴圈的版本
講回到遞迴,都必須搭配一個數字來計算第幾層
有從第一層加下去的,也有從最後一層加上來的
兩種版本也會附上
程式碼
Java
class Solution { // 從第一層加下去
public int maxDepth(TreeNode root) {
return maxDepth(root, 1);
}
private int maxDepth(TreeNode root, int nowLevel) {
if (root == null) {
return nowLevel -1;
}
return Math.max(maxDepth(root.left, nowLevel +1), maxDepth(root.right, nowLevel +1));
}
}
class Solution { // 從最後一層加上來
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) +1;
}
}
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int result = 0;
Queue queue = new LinkedList();
queue.offer(root);
while (!queue.isEmpty()) {
result++;
for (int i = 0, len = queue.size(); i < len; i++) {
TreeNode temp = (TreeNode)queue.poll();
if (temp.left != null) {
queue.offer(temp.left);
}
if (temp.right != null) {
queue.offer(temp.right);
}
}
}
return result;
}
}