leetcode

题目：Validate Binary Search Tree

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、BST有个特点（可以作为等价条件），即中序遍历是递增序列，可以通过中序遍历来判断一棵树是不是BST

2、设置一个变量pre记录中序遍历的前一个节点值，通过判断当前节点值与前一节点值来判定BST

代码（注释中为递归版本）：

 1 #include <stddef.h>
 2 #include <stack>
 3 
 4 using namespace std;
 5 
 6 struct TreeNode
 7 {
 8     int val;
 9     TreeNode *left;
10     TreeNode *right;
11     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
12 };
13 
14 class Solution
15 {
16 public:
17     bool isValidBST(TreeNode *root)
18     {
19         /*
20         int pre;
21 
22         valid = true;
23         first_node = true;
24         inorder(root, pre);
25 
26         return valid;
27         */
28 
29         stack<TreeNode *> treeNodeStack;
30         int pre;
31 
32         first_node = true;
33         while (root || !treeNodeStack.empty())
34         {
35             while (root)
36             {
37                 treeNodeStack.push(root);
38                 root = root->left;
39             }
40 
41             root = treeNodeStack.top();
42             treeNodeStack.pop();
43             if (!first_node)
44             {
45                 if (pre >= root->val)
46                 {
47                     return false;
48                 }
49             }
50             else
51             {
52                 first_node = false;
53             }
54             pre = root->val;
55             root = root->right;
56         }
57 
58         return true;
59     }
60 private:
61     bool valid;
62     bool first_node;
63     void inorder(TreeNode *root, int &pre)
64     {
65         if (!root)
66         {
67             return;
68         }
69         inorder(root->left, pre);
70         if (!first_node)
71         {
72             if (root->val <= pre)
73             {
74                 valid = false;
75             }
76         }
77         else
78         {
79             first_node = false;
80         }
81         pre = root->val;
82         inorder(root->right, pre);
83     }
84 };

View Code

网上查了几篇文章，看到有根据定义来解题的，即根节点值在左值和右值之间，然后更新左值和右值并且继续判断左子树和右子树，链接：http://www.cnblogs.com/remlostime/archive/2012/11/16/2772629.html

实践代码：

 1 #include <stddef.h>
 2 #include <stack>
 3 
 4 using namespace std;
 5 
 6 struct TreeNode
 7 {
 8     int val;
 9     TreeNode *left;
10     TreeNode *right;
11     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
12 };
13 
14 class Solution
15 {
16 public:
17     bool isValidBST(TreeNode *root)
18     {
19         /*
20         int pre;
21 
22         valid = true;
23         first_node = true;
24         inorder(root, pre);
25 
26         return valid;
27         */
28         /*
29         stack<TreeNode *> treeNodeStack;
30         int pre;
31 
32         first_node = true;
33         while (root || !treeNodeStack.empty())
34         {
35             while (root)
36             {
37                 treeNodeStack.push(root);
38                 root = root->left;
39             }
40 
41             root = treeNodeStack.top();
42             treeNodeStack.pop();
43             if (!first_node)
44             {
45                 if (pre >= root->val)
46                 {
47                     return false;
48                 }
49             }
50             else
51             {
52                 first_node = false;
53             }
54             pre = root->val;
55             root = root->right;
56         }
57 
58         return true;
59         */
60 
61         return isValid(root, INT_MIN, INT_MAX);
62     }
63 private:
64     bool isValid(TreeNode *root, int left, int right)
65     {
66         if (!root)
67         {
68             return true;
69         }
70         return root->val < right && root->val > left && isValid(root->left, left, root->val) && isValid(root->right, root->val, right);
71     }
72     bool valid;
73     bool first_node;
74     void inorder(TreeNode *root, int &pre)
75     {
76         if (!root)
77         {
78             return;
79         }
80         inorder(root->left, pre);
81         if (!first_node)
82         {
83             if (root->val <= pre)
84             {
85                 valid = false;
86             }
87         }
88         else
89         {
90             first_node = false;
91         }
92         pre = root->val;
93         inorder(root->right, pre);
94     }
95 };

View Code