一.題目描述
給定一個二叉樹,找出其最大深度。
二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。
說明: 葉子節點是指沒有子節點的節點。
示例:
給定二叉樹 [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
傳回它的最大深度 3 。
二.題目解析
public int maxDepth(TreeNode root) {
/*遞歸算法-深度優先搜尋dfs
時間O(n),空間O(h)
* */
if(root == null){
return 0;
}
return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
}
2.
public int maxDepth1(TreeNode root) {
/*疊代算法-廣度優先搜尋bfs
時間O(n),空間O(width)
* */
if(root == null){
return 0;
}
Queue queue = new LinkedList<>();
//初始進入根節點,高度是1
queue.offer(root);
int depth = 1;
while (!queue.isEmpty()){
//目前隊列大小(假設目前處理的是第i層所有節點)
int count = queue.size();
for (int i = 0; i < count; i++) {
//依次彈出第i層最前面的節點
TreeNode cur = (TreeNode)queue.poll();
//判斷左右孩子
if(cur.left != null){
queue.offer(cur.left);
}
if(cur.right != null){
queue.offer(cur.right);
}
}
//第i層所有節點已經出列,如果隊列不為空,說明有下一層節點,depth+1
if(queue.size() != 0){
depth++;
}
}
return depth;
}