資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++程式中，在二叉樹中找到最大子樹和，使得子樹也是BST
在這個問題中，我們給定一棵二叉樹BT。我們的任務是建立一個程式，在二叉樹中找到最大子樹和，使得子樹也是BST。
二叉樹有一個特殊條件，即每個節點最多可以有兩個子節點。
二叉搜尋樹是一棵樹，其中所有節點都遵循以下屬性
左子樹的鍵值小於其父節點（根節點）的鍵值。
右子樹的鍵值大於或等於其父節點（根節點）的鍵值。
讓我們舉個例子來理解這個問題，
輸入
輸出
32
解釋
這裡，我們有兩個是BST的子樹。它們的和是，
7 + 3 + 22 = 32 6 + 5 + 17 = 28 Maximum = 32.
解決方案
解決這個問題的一個簡單方法是遍歷樹資料結構，然後在每個節點處檢查其子節點是否可以形成二叉搜尋樹。如果我們找到所有構成BST的節點的和，然後返回找到的所有BSTSum中的最大值。
示例
程式說明解決方案的工作原理，
#include <bits/stdc++.h>
using namespace std;
int findMax(int a, int b){
if(a > b)
return a;
return b;
}
int findMin(int a, int b){
if(a > b)
return b;
return a;
}
struct Node {
struct Node* left;
struct Node* right;
int data;
Node(int data){
this−>data = data;
this−>left = NULL;
this−>right = NULL;
}
};
struct treeVal{
int maxVal;
int minVal;
bool isBST;
int sum;
int currMax;
};
treeVal CalcBSTSumTill(struct Node* root, int& maxsum){
if (root == NULL)
return { −10000, 10000, true, 0, 0 };
if (root−>left == NULL && root−>right == NULL) {
maxsum = findMax(maxsum, root−>data);
return { root−>data, root−>data, true, root−>data, maxsum };
}
treeVal LeftSTree = CalcBSTSumTill(root−>left, maxsum);
treeVal RightSTree = CalcBSTSumTill(root−>right, maxsum);
treeVal currTRee;
if (LeftSTree.isBST && RightSTree.isBST && LeftSTree.maxVal <
root−>data && RightSTree.minVal > root−>data) {
currTRee.maxVal = findMax(root−>data,
findMax(LeftSTree.maxVal, RightSTree.maxVal));
currTRee.minVal = findMin(root−>data,
findMin(LeftSTree.minVal, RightSTree.minVal));
maxsum = findMax(maxsum, RightSTree.sum + root−>data +
LeftSTree.sum);
currTRee.sum = RightSTree.sum + root−>data +
LeftSTree.sum;
currTRee.currMax = maxsum;
currTRee.isBST = true;
return currTRee;
}
currTRee.isBST = false;
currTRee.currMax = maxsum;
currTRee.sum = RightSTree.sum + root−>data + LeftSTree.sum;
return currTRee;
}
int CalcMaxSumBST(struct Node* root){
int maxsum = −10000;
return CalcBSTSumTill(root, maxsum).currMax;
}
int main(){
struct Node* root = new Node(10);
root−>left = new Node(12);
root−>left−>right = new Node(7);
root−>left−>right−>left = new Node(3);
root−>left−>right−>right = new Node(22);
root−>right = new Node(6);
root−>right−>left = new Node(5);
root−>right−>left−>right = new Node(17);
cout<<"The maximum sub−tree sum in a Binary Tree such that the
sub−tree is also a BST is "<<CalcMaxSumBST(root);
return 0;
}輸出
The maximum sub−tree sum in a Binary Tree such that the sub−tree is also a BST is 32
更新於： 2020-12-09
97 次檢視
廣告