Licking Exercise - 60 Maximum key-value sum of binary search subtrees

60 二叉搜索子树的最大键值和

1.问题描述
给你一棵以 root 为根的 二叉树 （注意：不一定是二叉搜索树）,Would you please return any binary search subtree of the biggest keys and.

二叉搜索树的定义如下：

任意节点的左子树中的键值都 小于 此节点的键值.

任意节点的右子树中的键值都 大于 此节点的键值.

任意节点的左子树和右子树都是二叉搜索树.

示例 1：

输入：root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]

输出：20

解释：因为以1For the root of binary tree is not a binary search tree,So the key value is zero 3 的子树是和最大的二叉搜索树.

示例 2：

输入：root = [4,3,null,1,2]

输出：2

解释：因为以3或4For the root of binary tree is not a binary search tree,So the key value is zero 2 的单节点子树是和最大的二叉搜索树.

示例 3：

输入：root = [-4,-2,-5]

输出：0

解释：所有节点键值都为负数,和最大的二叉搜索树为空.

示例 4：

输入：root = [2,1,3]

输出：6

示例 5：

输入：root = [5,4,8,3,null,6,3]

输出：7

说明：

每棵树最多有 20000 个节点.

每个节点的键值在 [-10^4 , 10^4] 之间.

可使用以下main函数：

#include

#include

#include

#include

#include

#include

#include

using namespace std;

struct TreeNode

{

int val;

TreeNode *left;

TreeNode *right;

TreeNode() : val(0), left(NULL), right(NULL) {}

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

};

TreeNode* inputTree()

{

int n,count=0;

char item[100];

cin>>n;

if (n==0)

    return NULL;

cin>>item;

TreeNode* root = new TreeNode(atoi(item));

count++;

queue<TreeNode*> nodeQueue;

nodeQueue.push(root);

while (count<n)

{

    TreeNode* node = nodeQueue.front();

    nodeQueue.pop();

    cin>>item;

    count++;

    if (strcmp(item,"null")!=0)

    {

        int leftNumber = atoi(item);

        node->left = new TreeNode(leftNumber);

        nodeQueue.push(node->left);

    }

    if (count==n)

        break;

    cin>>item;

    count++;

    if (strcmp(item,"null")!=0)

    {

        int rightNumber = atoi(item);

        node->right = new TreeNode(rightNumber);

        nodeQueue.push(node->right);

    }

}

return root;

}

int main()

{

TreeNode* root;

root=inputTree();

int res=Solution().maxSumBST(root);

cout<<res;

}

2.输入说明
首先输入结点的数目n（注意,这里的结点包括题中的null空结点,所以这里的n可能超过20000）

然后输入n个结点的数据,需要填充为空的结点,输入null.
3.输出说明
输出一个整数
4.范例
输入
15
1 4 3 2 4 2 5 null null null null null null 4 6
输出
20
5.代码

#include <iostream>

#include <queue>

#include <stack>

#include<cstdlib>

#include <climits>

#include <cstring>

#include<map>

using namespace std;

struct TreeNode

{
    

	int val;

	TreeNode *left;

	TreeNode *right;

	TreeNode() : val(0), left(NULL), right(NULL) {
    }

	TreeNode(int x) : val(x), left(NULL), right(NULL) {
    }

	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {
    }

};

TreeNode* inputTree()

{
    

	int n, count = 0;

	char item[100];

	cin >> n;

	if (n == 0)

		return NULL;

	cin >> item;

	TreeNode* root = new TreeNode(atoi(item));

	count++;

	queue<TreeNode*> nodeQueue;

	nodeQueue.push(root);

	while (count < n)

	{
    

		TreeNode* node = nodeQueue.front();

		nodeQueue.pop();

		cin >> item;

		count++;

		if (strcmp(item, "null") != 0)

		{
    

			int leftNumber = atoi(item);

			node->left = new TreeNode(leftNumber);

			nodeQueue.push(node->left);

		}

		if (count == n)

			break;

		cin >> item;

		count++;

		if (strcmp(item, "null") != 0)

		{
    

			int rightNumber = atoi(item);

			node->right = new TreeNode(rightNumber);

			nodeQueue.push(node->right);

		}

	}

	return root;

}

int res = INT_MIN;

vector<int> dfs(TreeNode* node) {
    

	if (node==NULL) //Note here in front of the two values cannot write back
		return {
     INT_MAX, INT_MIN, 0, true };//Four elements are respectively the minimum ,最大值 ,总和 ,是否为搜索二叉树

	auto leftVec = dfs(node->left);//遍历左子树
	auto rightVec = dfs(node->right);//遍历右子树
	// Update the current subtree and
	int sum = leftVec[2] + rightVec[2] + node->val;
	bool isBitree = false;
	// Is greater than the left subtree maximum,That is larger than left subtree all elements
	// 小于右子树最小值,Than right subtree all elements are small
	if (node->val > leftVec[1] && node->val < rightVec[0]) {
    
		// The left tree and right subtree is binary search tree
		if (leftVec[3] && rightVec[3]) {
    
			isBitree = true;
		}
	}
	if (isBitree) res = max(res, sum);
	// Update the current subtree of the maximum and the minimum
	int maxVal = max(max(leftVec[1], rightVec[1]), node->val);
	int minVal = min(min(leftVec[0], rightVec[0]), node->val);
	return {
     minVal, maxVal, sum, isBitree };//返回

}
int maxSumBST(TreeNode *root)
{
    
	dfs(root);
	return res > 0 ? res : 0;
}
int main()

{
    

	TreeNode* root;

	root = inputTree();

	int res = maxSumBST(root);

	cout << res;

}