我在这个问题上犯了个错误，一开始我仅仅把二叉树三个节点对比大小，可能造成二叉树局部三个节点符合BST树特性，但是放在全局就不符合了。因此我们要记录min_node和max_node，从顶层递归到下层。而不是从下层开始，仅仅因为三个节点满足就返回true。
典型情况：
10 / / 4 15 / / / /2 5 6 17如上图，15，6，17局部满足BST树，但是6<10，所以不是BST树。
我的错误解法：
class Solution {public: bool isValidBST(TreeNode* root) { return root != NULL ? is_bst(root) : true; } bool is_bst(TreeNode* root){ if(root->left == NULL && root->right == NULL) return true; else if(root->left == NULL) return is_bst(root->right); else if(root->right == NULL) return is_bst(root->left); else return is_bst(root->left) && is_bst(root->right) && (root->left->val <= root->val && root->right->val > root->val); }};实际上错误解法通过了80%的case。
下面说正确解法。方法一： 利用BST树的特性，从上往下递归，记录min_node和max_node，对左子树来说，只需记录max_node，即它的父节点；同理对于右字数，只需记录min_node。然后它们满足BST关系即可。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: bool isValidBST(TreeNode* root) { return root != NULL ? is_bst(root, NULL, NULL) : true; } bool is_bst(TreeNode* root, TreeNode* min_node, TreeNode* max_node){ if(root == NULL) return true; if(min_node != NULL && root->val <= min_node->val || max_node != NULL && root->val >= max_node->val) return false; //if false, stop and return return is_bst(root->left, min_node, root) && is_bst(root->right, root, max_node); }};方法二：利用中序遍历关系。由于BST树的中序遍历是有序的，所以我们用中序遍历来做文章。
class Solution {public: bool isValidBST(TreeNode* root) { TreeNode* PRev = NULL; return is_bst(root, prev); } bool is_bst(TreeNode* root, TreeNode*& prev){ if(root == NULL) return true; if(!is_bst(root->left, prev)) return false; if(prev != NULL && prev->val >= root->val) return false; prev = root; return is_bst(root->right, prev); }};利用prev节点一开始为NULL，后来作为中序遍历的前一个节点，和当前节点进行比较判断是否满足BST特性即可。
唉，人生苦短，我用Python :)
# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution(object): def isValidBST(self, root): self.prev = None return self.is_bst(root, self.prev) def is_bst(self, root, prev): if root == None: return True if not self.is_bst(root.left, self.prev): return False if self.prev != None and self.prev.val >= root.val: return False self.prev = root return self.is_bst(root.right, self.prev)新闻热点
疑难解答
