資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++程式：求二叉樹最深節點之和
假設我們有一個二叉樹；我們需要找到其最深葉子節點的值之和。例如，如果樹如下所示：
則輸出為11。
為了解決這個問題，我們將遵循以下步驟：
定義一個map m和maxDepth
定義一個遞迴方法solve()，它將接收節點和層級作為引數，初始層級為0
如果節點不存在，則返回
maxDepth := level 和 maxDepth 的最大值
m[level] 加上節點的值
solve(節點的左子節點, level + 1)
solve(節點的右子節點, level + 1)
在主方法中，設定 maxDepth := 0，然後 solve(根節點, 0)
返回 m[maxDepth]
讓我們看看下面的實現，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = NULL;
right = NULL;
}
};
class Solution {
public:
int maxDepth;
map <int, int> m;
void solve(TreeNode* node, int level = 0){
if(!node)return;
maxDepth = max(level, maxDepth);
m[level] += node->val;
solve(node->left, level + 1);
solve(node->right, level + 1);
}
int deepestLeavesSum(TreeNode* root) {
maxDepth = 0;
m.clear();
solve(root);
return m[maxDepth];
}
};
main(){
TreeNode *root = new TreeNode(1);
root−>left = new TreeNode(2);
root−>right = new TreeNode(3);
root−>left−>left = new TreeNode(4);
root−>left−>right = new TreeNode(5);
root−>right−>right = new TreeNode(6);
root−>right−>right−>right = new TreeNode(4);
root−>left−>left−>left = new TreeNode(7);
Solution ob;
cout << (ob.deepestLeavesSum(root));
}輸入
TreeNode *root = new TreeNode(1); root−>left = new TreeNode(2); root−>right = new TreeNode(3); root−>left−>left = new TreeNode(4); root−>left−>right = new TreeNode(5); root−>right−>right = new TreeNode(6); root−>right−>right−>right = new TreeNode(4); root−>left−>left−>left = new TreeNode(7);
輸出
11
更新於：2020年10月21日
81 次瀏覽
廣告