博客

98. Validate Binary Search Tree

如题验证一个树是否是搜索树，搜索树的性质在这里就不说了，那首先想到一个简单的就是递归中序遍历，如果出来的这个数组不是有序的，那么这棵树必然不是一个搜索树，这是一个做法，但是如果门不使用额外空间，并且采用递归的方式判断一棵树是否是搜索树的条件是什么，在从root节点递归到左子树中时候，左子树中最大的节点，也就是左子树中最右边的节点需要小于root节点，同时每一个节点的左右子节点满足搜索树，那么同理右子树需要知道root节点右子树的最小节点大于root节点，因此我们需要一个前序节点来保存root节点递归到下一层之前那一个状态。具体代码如下：

class Solution {
public:
	bool isValidBST(TreeNode* root) {
		TreeNode* prev = NULL;
		bool res = true;
		validate(root, prev, res);
		return res;
	}
	void validate(TreeNode* node, TreeNode*& prev, bool& res) {
		if (node == nullptr)
			return;
		validate(node->left, prev, res);
		if (prev != nullptr && node->val <= prev->val)
		{
			res = false;
			return;
		}
		prev = node;
		validate(node->right, prev, res);
	}
};

注意这里的prev节点是一个引用，因此他是一个全局都可以使用的节点。