数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 C++ 中计算二叉树中的最大值根数
假设我们有一个二叉树 root，我们必须计算结点数，其中其值大于或等于其所有后代的值。
因此，如果输入如下
则输出将为 4，因为除 3 之外的所有结点都满足条件。
为了解决这个问题，我们将遵循以下步骤 −
定义一个函数 dfs()，它将获取结点，
如果结点不为空，则 −
返回 0
l := dfs(结点的左结点)
r := dfs(结点的右结点)
如果结点的 val >= l 和 r 的最大值，则 −
(将 ret 增加 1)
x := 结点、l 和 r 的 val 中的最大值
返回 x
在主方法中，执行以下操作
ret := 0
dfs(root)
返回 ret
让我们看看以下实现以获得更好的理解 −
示例
#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 ret;
int dfs(TreeNode* node){
if(!node)
return 0;
int l = dfs(node->left);
int r = dfs(node->right);
if(node->val >= max(l, r)) {
ret++;
}
int x = max({node->val, l, r});
return x;
}
int solve(TreeNode* root) {
ret = 0;
dfs(root);
return ret;
}
};
main(){
Solution ob;
TreeNode *root = new TreeNode(7);
root->left = new TreeNode(4);
root->right = new TreeNode(3);
root->right->left = new TreeNode(7);
root->right->right = new TreeNode(5);
cout << (ob.solve(root));
}输入
TreeNode *root = new TreeNode(7); root->left = new TreeNode(4); root->right = new TreeNode(3); root->right->left = new TreeNode(7); root->right->right = new TreeNode(5);
输出
4
更新时间： 2020 年 9 月 2 日
127 次浏览
广告