劍指 Offer 55 – I. 二叉樹的深度
劍指 Offer 55 – I. 二叉樹的深度
輸入一棵二叉樹的根節點，求該樹的深度。從根節點到葉節點依次經過的節點（含根、葉節點）形成樹的一條路徑，最長路徑的長度為樹的深度。
例如：
給定二叉樹 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
提示：
節點總數 <= 10000
注意：本題與主站 104 題相同：//leetcode-cn.com/problems/maximum-depth-of-binary-tree/
1、BFS（層次遍歷）
其實還是有點套模板的嫌疑，比如
for(TreeNode node : queue) {
if(node.left != null) tmp.add(node.left);
if(node.right != null) tmp.add(node.right);
}。總的來說就是多練多熟悉吧。
public int maxDepth(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int res = 0;
while (!queue.isEmpty()) {
res++;
int n = queue.size();
for (int i = 0; i < n; i++) {
TreeNode node = queue.poll();
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
}
return res;
}
這個是K神的思路，他加了個LinkedList<>()
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) return 0;
List<TreeNode> queue = new LinkedList<>() {{ add(root); }}, tmp;
int res = 0;
while(!queue.isEmpty()) {
tmp = new LinkedList<>();
for(TreeNode node : queue) {
if(node.left != null) tmp.add(node.left);
if(node.right != null) tmp.add(node.right);
}
queue = tmp;
res++;
}
return res;
}
}
二、遞歸
maxDepth(root.left)計算左節點的深度，maxDepth(root.right)計算右節點的深度。
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return Math.max(left + 1, right + 1);
}
}
這是K神的思路，直接把4行變成2行，k神yyds。
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
參考鏈接：
