資料結構
網路
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 次瀏覽
廣告