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
廣告