BT 3 validate, unique, recover

Validate Binary Search Tree

 

浪费太多时间思考这个问题，结果知道了左孩子的右孩子必须比爷爷小，右孩子的左孩子必须比爷爷大，可是这么递归是超时的，实际上是归纳成先序遍历，递归判断，递归时传入两个参数，一个是左界，一个是右界，节点的值必须在两个界的中间，同时在判断做子树和右子树时更新左右界。

class Solution {
public:
 bool ValidBST(TreeNode* node, int leftVal, int rightVal)
 {
	 if(node == NULL)
		 return true;

	 return leftVal < node->val && node->val < rightVal && ValidBST(node->left, leftVal,node->val) && ValidBST(node->right,node->val,rightVal);
 }
bool isValidBST(TreeNode *root) 
{
	if(root == NULL || root->left == NULL&& root->right == NULL)
		return true;
	return ValidBST(root,INT_MIN,INT_MAX);
}
};

Unique Binary Search Trees II 

主要就是怎么实现左边小于父亲，右边大于父亲，左右子树分别建立，DFS实现

class Solution {
public:
vector<TreeNode *> generateTrees(int start, int end)
{
	vector<TreeNode *> results;
	if(start > end)
	{
		results.push_back(NULL);
		return results;
	}
	for(int k = start; k <= end; ++ k)
	{
		vector<TreeNode *> left = generateTrees(start, k-1);
		vector<TreeNode *> right = generateTrees(k+1,end);
		for(int i = 0; i < left.size(); ++ i)
			for(int j = 0; j < right.size(); ++ j)
			{
				TreeNode* node = new TreeNode(k);
				node->left = left[i];
				node->right = right[j];
				results.push_back(node);
			}
	}
	return results;
}


vector<TreeNode *> generateTrees(int n) 
{
	vector<TreeNode *> results;
	if(n == 0)
	{
	    results.push_back(NULL);
	    return results;
	}
	
	return generateTrees(1,n);
}
};

Recover Binary Search Tree

完全参考的别人的代码，因为想不出来

class Solution {
public:
//当对树采用中序遍历，可以得到一个有序序列，每个节点都是小于后面的大于前面的，假设是123456，交换两个节点
//得到1,2,4,3,5,6或者是1,2,3,6,5,4 无序的两点的规律就是第一个比后面节点大的，和
//下一个出错的节点是最后（很重要是最后一个）一个比前面节点小的节点，就是这个规律，关键即使归纳出规律
void findTwoNodes(TreeNode* node, TreeNode* &n1, TreeNode* &n2, TreeNode* &pre)
{
	if(node == NULL)
		return;
	//左根右，中序遍历
	findTwoNodes(node->left,n1,n2,pre);//遍历左子树,从左子树返回的时候，pre节点是node的左边孩子，node是根
	if(pre != NULL && pre->val > node->val)
	{
		n2 = node;
		if(n1 == NULL)
			n1 = pre;
	}
	pre = node;//pre节点保存当前根节点
	findTwoNodes(node->right,n1,n2,pre);//遍历右子树,也是往右子树的左边一直往下走，走到叶子，与pre比较，其应该大于pre，此时pre是根，node是右边节点

}

void recoverTree(TreeNode *root)
{
	if(root == NULL)
		return;
	//保存出错的节点

	TreeNode* n1 = NULL;
	TreeNode* n2 = NULL;
	TreeNode* pre = NULL;
	findTwoNodes(root,n1,n2,pre);
	int temp = 0;
	if(n1 != NULL && n2 != NULL)
	{
	    temp = n1->val;
	    n1->val = n2->val;
	    n2->val = temp;
	}
}
};