98. Validate Binary Search Tree（判断合法二叉搜索树）

2019-11-14 08:45:51

字体：大中小

来源：转载

供稿：网友

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.Example 1: 2 / / 1 3Binary tree [2,1,3], return true.Example 2: 1 / / 2 3Binary tree [1,2,3], return false.

我在这个问题上犯了个错误，一开始我仅仅把二叉树三个节点对比大小，可能造成二叉树局部三个节点符合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)

上一篇：通道

下一篇：C++入门引用详解