欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

不同的二叉搜索树

程序员文章站 2022-07-15 11:59:53
...

题目

不同的二叉搜索树

思路

一开始也有想到对于任意一个值i,可以求出它左边范围内有多少种树的组合,右边范围有多少种树的组合,但无奈编程水平有限,不能很好的表达出来(我太菜了)
相关代码如下:

class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
		vector<TreeNode*> v;
		if (n)
			return TreeChild(1, n);
		else
			return v;
	}
	vector<TreeNode*> TreeChild(int left,int right) {
		vector<TreeNode*> res;
		//如果左边界大于右边界,说明已无节点
		if (left > right) {
			res.push_back(NULL);
			return res;
		}
		for (int i = left; i <= right; i++) {
			vector<TreeNode*> leftchild = TreeChild(left, i - 1);//存储不同的左子树
			vector<TreeNode*> rightchild = TreeChild(i + 1, right);//存储不同的右子树
			for (auto& s : leftchild) {
				for (auto& t : rightchild) {
					TreeNode* tre = new TreeNode(i);
					tre->left = s;
					tre->right = t;
					res.push_back(tre);
				}
			}
		}
		return res;
	}
};

这个题目的大体思路是这样的:给定一个范围,对于范围中的每一个值都可以作为根节点,那么他的左子树就是左边范围值所构成的二叉搜索树,右子树就是右边范围所构成的二叉搜索树,这又是同一个问题,那么我们就可以使用递归解决,然后左子树和右子树相组合,就可以得到范围中的某值i作为根节点能构成几种二叉搜索树,然后对该范围内的值都是用类似的思路求解即可

首先设置递归的基准条件,如果左边界大于右边界,则返回NULL

if (left > right) {
			res.push_back(NULL);
			return res;
		}

然后关键在于某值i作为根节点时它左子树和右子树的组合:

for (int i = left; i <= right; i++) {
			vector<TreeNode*> leftchild = TreeChild(left, i - 1);//存储不同的左子树
			vector<TreeNode*> rightchild = TreeChild(i + 1, right);//存储不同的右子树
			//进行左子树和右子树的组合
			for (auto& s : leftchild) {
				for (auto& t : rightchild) {
					TreeNode* tre = new TreeNode(i);
					tre->left = s;
					tre->right = t;
					res.push_back(tre);
				}
			}
		}

总结

这道题是给定一个范围求出该范围能构成几种二叉搜索树,那么我们就要知道,二叉搜索树就是:左子树所有节点关键值都要小于该节点的关键值,右子树所有节点关键值都要大于该节点的关键值,然后给定的范围的隐含条件是:该序列是一个递增序列,那么我们就可以从这两个条件入手。

相关标签: LeetCode