Valid Binary Tree@leetcode

刷题必备书籍：Cracking the Coding Interview: 150 Programming Questions and Solutions 

简历：The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍：Introduction to Algorithms
编程珠玑：Programming Pearls (2nd Edition)
C++ 学习：The C++ Programming Language, 4th Edition
经典操作系统书籍，龙书：Operating System Concepts
创业：The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

» Solve this problem

这个题思路比较简单，就是看左右子树是否符合BST的条件。但是，有一点需要注意的就是，左子树的所有结点都要比root小，右子树的所有结点都要比root大。这样就给了比较的时候一个range，范围，我们在递归的时候要把这个范围给传递进去。

	/**
	* Definition for binary tree
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	bool validBST(TreeNode *node, int MIN, int MAX)
	{
	if(node==NULL) return true;
	if(node->val<MAX&&node->val>MIN&&validBST(node->left,MIN,node->val)&&validBST(node->right,node->val, MAX))
	return true;
	else
	return false;
	}
	bool isValidBST(TreeNode *root) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	return validBST(root, INT_MIN, INT_MAX);
	}
	};

view raw Valid Binary Tree hosted with ❤ by GitHub