数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++实现二叉树的最大和BST
假设我们有一个二叉树根节点，我们需要找到任何子树的所有节点的最大和，该子树同时也是一个二叉搜索树 (BST)。
例如，如果输入如下：
则输出为 20，这是所选 BST 中所有节点的总和。
为了解决这个问题，我们将遵循以下步骤：
创建一个名为 Data 的结构体，它将包含一些成员，例如 sz、maxVal、minVal、ok 和 sum。 还定义一个 Data 结构体的初始化函数，参数顺序为 (sz, minVal, maxVal, ok)，并将 sum 设置为 0。
ret := 0
定义一个名为 solve() 的方法，该方法将接收树的根节点。
如果节点为空或节点的值为 0，则：
返回一个使用 (0, inf, -inf, true) 初始化的新 Data 结构体。
left := solve(节点的左子树)
right := solve(节点的右子树)
创建一个名为 curr 的 Data 类型实例
curr.ok := false
如果节点的值 >= right.minVal，则：
返回 curr
如果节点的值 <= left.maxVal，则：
返回 curr
如果 left.ok 和 right.ok 为真，则：
curr.sum := 节点的值 + left.sum + right.sum
ret := curr.sum 和 ret 的最大值
curr.sz := 1 + left.sz + right.sz
curr.ok := true
curr.maxVal := 节点值和 right.maxVal 的最大值
curr.minVal := 节点值和 left.minVal 的最小值
返回 curr
在主方法中执行以下操作：
ret := 0
solve(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;
}
};
void insert(TreeNode **root, int val){
queue<TreeNode*> q;
q.push(*root);
while(q.size()){
TreeNode *temp = q.front();
q.pop();
if(!temp->left){
if(val != NULL)
temp->left = new TreeNode(val);
else
temp->left = new TreeNode(0);
return;
}else{
q.push(temp->left);
}
if(!temp->right){
if(val != NULL)
temp->right = new TreeNode(val);
else
temp->right = new TreeNode(0);
return;
}else{
q.push(temp->right);
}
}
}
TreeNode *make_tree(vector<int> v){
TreeNode *root = new TreeNode(v[0]);
for(int i = 1; i<v.size(); i++){
insert(&root, v[i]);
} return root;
}
struct Data{
int sz;
int maxVal;
int minVal;
bool ok;
int sum;
Data(){}
Data(int a, int b, int c, bool d){
sz = a;
minVal = b;
maxVal = c;
ok = d;
sum = 0;
}
};
class Solution {
public:
int ret = 0;
Data solve(TreeNode* node){
if (!node || node->val == 0)
return Data(0, INT_MAX, INT_MIN, true);
Data left = solve(node->left);
Data right = solve(node->right);
Data curr;
curr.ok = false;
if (node->val >= right.minVal) {
return curr;
}
if (node->val <= left.maxVal) {
return curr;
}
if (left.ok && right.ok) {
curr.sum = node->val + left.sum + right.sum;
ret = max(curr.sum, ret);
curr.sz = 1 + left.sz + right.sz;
curr.ok = true;
curr.maxVal = max(node->val, right.maxVal);
curr.minVal = min(node->val, left.minVal);
}
return curr;
}
int maxSumBST(TreeNode* root){
ret = 0;
solve(root);
return ret;
}
};
main(){
Solution ob;
vector<int> v =
{1,4,3,2,4,2,5,NULL,NULL,NULL,NULL,NULL,NULL,4,6};
TreeNode *root = make_tree(v);
cout << (ob.maxSumBST(root));
}输入
{1,4,3,2,4,2,5,NULL,NULL,NULL,NULL,NULL,NULL,4,6}输出
20
368 次浏览
