数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会学
时尚研究
法律研究最大子树和，其中子树也是二叉查找树，用 C++ 实现
在本教程中，我们将讨论一个程序，该程序找到二叉树中最大子树和，其中子树也是二叉查找树。
为此，我们将提供一棵二叉树。我们的任务是打印一个子树的和，该子树也是二叉搜索树。
示例
#include <bits/stdc++.h>
using namespace std;
//creating binary tree node
struct Node {
struct Node* left; struct Node* right; int data;
Node(int data) {
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
struct Info {
int max;
int min;
bool isBST;
int sum;
int currmax;
};
Info MaxSumBSTUtil(struct Node* root, int& maxsum) {
if (root == NULL) return { INT_MIN, INT_MAX, true, 0, 0 };
if (root->left == NULL && root->right == NULL) {
maxsum = max(maxsum, root->data);
return { root->data, root->data, true, root->data, maxsum };
}
Info L = MaxSumBSTUtil(root->left, maxsum);
Info R = MaxSumBSTUtil(root->right, maxsum);
Info BST;
if (L.isBST && R.isBST && L.max < root->data && R.min > root->data) {
BST.max = max(root->data, max(L.max, R.max));
BST.min = min(root->data, min(L.min, R.min));
maxsum = max(maxsum, R.sum + root->data + L.sum);
BST.sum = R.sum + root->data + L.sum;
BST.currmax = maxsum;
BST.isBST = true;
return BST;
}
BST.isBST = false;
BST.currmax = maxsum;
BST.sum = R.sum + root->data + L.sum;
return BST;
}
int MaxSumBST(struct Node* root) {
int maxsum = INT_MIN;
return MaxSumBSTUtil(root, maxsum).currmax;
}
int main() {
struct Node* root = new Node(5);
root->left = new Node(14);
root->right = new Node(3);
root->left->left = new Node(6);
root->right->right = new Node(7);
root->left->left->left = new Node(9);
root->left->left->right = new Node(1);
cout << MaxSumBST(root);
return 0;
}输出
10
更新于: 2020 年 7 月 10 日
153 次浏览
广告