您好,登錄后才能下訂單哦!
本文小編為大家詳細(xì)介紹“C++怎么實現(xiàn)二叉樹的最大深度”,內(nèi)容詳細(xì),步驟清晰,細(xì)節(jié)處理妥當(dāng),希望這篇“C++怎么實現(xiàn)二叉樹的最大深度”文章能幫助大家解決疑惑,下面跟著小編的思路慢慢深入,一起來學(xué)習(xí)新知識吧。
Example:
Given binary tree [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
return its depth = 3.
求二叉樹的最大深度問題用到深度優(yōu)先搜索 Depth First Search,遞歸的完美應(yīng)用,跟求二叉樹的最小深度問題原理相同,參見代碼如下:
C++ 解法一:
class Solution { public: int maxDepth(TreeNode* root) { if (!root) return 0; return 1 + max(maxDepth(root->left), maxDepth(root->right)); } };
Java 解法一:
public class Solution { public int maxDepth(TreeNode root) { return root == null ? 0 : (1 + Math.max(maxDepth(root.left), maxDepth(root.right))); } }
我們也可以使用層序遍歷二叉樹,然后計數(shù)總層數(shù),即為二叉樹的最大深度,注意 while 循環(huán)中的 for 循環(huán)的寫法有個 trick,一定要將 q.size() 放在初始化里,而不能放在判斷停止的條件中,因為q的大小是隨時變化的,所以放停止條件中會出錯,參見代碼如下:
C++ 解法二:
class Solution { public: int maxDepth(TreeNode* root) { if (!root) return 0; int res = 0; queue<TreeNode*> q{{root}}; while (!q.empty()) { ++res; for (int i = q.size(); i > 0; --i) { TreeNode *t = q.front(); q.pop(); if (t->left) q.push(t->left); if (t->right) q.push(t->right); } } return res; } };
Java 解法二:
public class Solution { public int maxDepth(TreeNode root) { if (root == null) return 0; int res = 0; Queue<TreeNode> q = new LinkedList<>(); q.offer(root); while (!q.isEmpty()) { ++res; for (int i = q.size(); i > 0; --i) { TreeNode t = q.poll(); if (t.left != null) q.offer(t.left); if (t.right != null) q.offer(t.right); } } return res; } }
讀到這里,這篇“C++怎么實現(xiàn)二叉樹的最大深度”文章已經(jīng)介紹完畢,想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領(lǐng)會,如果想了解更多相關(guān)內(nèi)容的文章,歡迎關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。