截止到目前我已經寫了 600多道演算法題，其中部分已經整理成了pdf檔案，目前總共有1000多頁（并且還會不斷的增加），大家可以免費下載
下載鏈接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取碼：6666
這題讓求的是最深葉子節點的和，最容易想到的就BFS解決，也就是一層一層的從上往下遍歷，BFS的遍歷方式如下，也可以看下373，資料結構-6,樹
到最后一層的時候我們再把節點的值相加即可，這里我們不知道哪一層是最深的層數，我們可以把每一層所有節點的值都相加，下一層會把上一次的給覆寫掉，最后一層下面沒有了，所以沒法覆寫，直接回傳即可，來看下代碼
public int deepestLeavesSum(TreeNode root) {
//每層節點的和
int res = 0;
//佇列
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
//佇列不為空，繼續訪問佇列的元素
while (!queue.isEmpty()) {
//當前層的節點數量
int levelCount = queue.size();
//當前層所有節點值的和
res = 0;
//遍歷當前層的所有節點
for (int j = 0; j < levelCount; j++) {
TreeNode node = queue.poll();
//累加當前層節點的值
res += node.val;
//如果左子節點不為空就把他加入到佇列中
if (node.left != null)
queue.add(node.left);
//如果右子節點不為空就把他加入到佇列中
if (node.right != null)
queue.add(node.right);
}
}
return res;
}
時間復雜度：O(N)，N是節點的個數，所有節點都要訪問一遍
空間復雜度：O(N)，佇列中存放的是每層節點的個數，滿二叉樹的時候最后一層節點的個數是（N+1）/2
//記錄樹的最大深度
private int maxLevel = 0;
//記錄最后一層所有節點的和
private int sum = 0;
public int deepestLeavesSum(TreeNode root) {
dfs(root, 0);
return sum;
}
//level表示第幾層，根節點是第0層
private void dfs(TreeNode root, int level) {
//邊界條件判斷，如果是空直接回傳
if (root == null)
return;
//操作當前節點，如果沒到最后一層，記錄
//當前訪問過的最大層數，并且把sum重置為0，
//也就是之前加的作廢
if (level > maxLevel) {
maxLevel = level;
sum = 0;
}
//如果到了最后一層，就把節點值相加
if (level == maxLevel) {
sum = sum + root.val;
}
//訪問左子節點和右子節點，
dfs(root.left, level + 1);
dfs(root.right, level + 1);
}
時間復雜度：O(N)，N是樹的所有節點個數
空間復雜度：O(H)，H是樹的最大深度
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/302221.html
標籤：java
上一篇：快速冪