数据结构
网络
关系数据库管理系统 (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 次浏览
广告