【ATT】Validate Binary Search Tree

Q: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.

1 bool helper(TreeNode *root,TreeNode* &leftnail,TreeNode *&rightnail)
 2 {
 3     if(!root)
 4     {
 5         leftnail = rightnail = NULL;
 6         return true;
 7     }
 8 
 9     bool bFlag = false;
10     TreeNode *left_left,*left_right,*right_left,*right_right;
11     left_left = left_right = right_left = right_right = NULL;
12     if(helper(root->left,left_left,left_right)&&helper(root->right,right_left,right_right))
13     {
14         if((!left_right||left_right->val<root->val)&&(!right_left||right_left->val>root->val))
15             bFlag = true;
16         leftnail = left_left?left_left:root;
17         rightnail = right_right?right_right:root;
18     }
19     return bFlag;
20 
21 }
22 bool isValidBST(TreeNode *root) {
23     // Start typing your C/C++ solution below
24     // DO NOT write int main() function
25     TreeNode *leftnail,*rightnail;
26     leftnail = rightnail = NULL;
27     return helper(root,leftnail,rightnail);
28 
29 }

原文链接: https://www.cnblogs.com/summer-zhou/archive/2013/05/30/3108760.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍