資訊專欄INFORMATION COLUMN
LeetCode 104 Maximum Depth of Binary Tree
難度：Easy
題目描述：
找到一顆二叉樹的最深深度。
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Note: A leaf is a node with no children.
Example:
Given binary tree [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
return its depth = 3.
解題思路：
Solution 1：
解二叉樹的題目一般如果難度為easy，則要求iterative和recursive都會寫，二叉樹的最深深度是左子樹和右子樹的Max深度，根據這一特性，我們自底向上，時間復雜度O(n), Space O(1), 但因為是遞歸，所以會占用stack，recursive的寫法如下：
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
//get the left and right depth
int leftDep = maxDepth(root.left);
int rightDep = maxDepth(root.right);
return 1 + Math.max(leftDep, rightDep);
}
解題思路：
Solution 2：
使用BFS方法iterative使用一個Queue，每往下一層都加1，最后拿到最深深度。
時間：O(n), 空間 O(n)
public int maxDepth(TreeNode root) {
//iterative
if (root == null) return 0;
Queue q = new LinkedList<>();
q.offer(root);
int dep = 0;
while(!q.isEmpty()) {
dep++;
int size = q.size();
for(int i = 0; i < size; i++) {
TreeNode now = q.poll();
if (now.left != null) q.offer(now.left);
if (now.right != null) q.offer(now.right);
}
}
return dep;
}
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/71797.html
摘要：小鹿題目二叉樹的最大深度給定一個二叉樹，找出其最大深度。二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。求二叉樹的深度，必然要用到遞歸來解決。分別遞歸左右子樹。 Time：2019/4/22Title: Maximum Depth of Binary TreeDifficulty: MediumAuthor:小鹿 題目：Maximum Depth of Binary Tre...
摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。 這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。 在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...
摘要：微信公眾號記錄截圖記錄截圖目前關于這塊算法與數據結構的安排前。已攻略返回目錄目前已攻略篇文章。會根據題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協議授權之外的使用權限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目錄 不...
摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經到題，所以后面會調整自己，在刷算法與數據結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚有什么區別...
摘要：題目鏈接題目分析返回給定的二叉樹有多少層。思路每下一級，層樹，并記錄到類屬性中。并判斷是否大于已知最深層樹。最終代碼若覺得本文章對你有用，歡迎用愛發電資助。 104. Maximum Depth of Binary Tree 題目鏈接 104. Maximum Depth of Binary Tree 題目分析 返回給定的二叉樹有多少層。 思路 每下一級，層樹+1，并記錄到類屬性lev...
閱讀 3163·2021-11-22 14:45
閱讀 3313·2019-08-29 13:11
閱讀 2315·2019-08-29 12:31
閱讀 934·2019-08-29 11:21
閱讀 3000·2019-08-29 11:09
閱讀 3628·2019-08-28 18:11
閱讀 1432·2019-08-26 13:58
閱讀 1283·2019-08-26 13:27
