LeetCode 98: 验证二叉搜索树

guodongxiaren commented 4 years ago

验证二叉树是否是二叉搜索树（BST）

https://leetcode-cn.com/problems/validate-binary-search-tree

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:

    2
   / \
  1   3

输出: true

示例 2:

输入:

输出: false 解释: 输入为: [5,1,4,null,null,3,6]。根节点的值为 5 ，但是其右子节点值为 4 。

guodongxiaren commented 4 years ago

递归解法

/**
 * 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) { /* 原函数声明 */
    bool isValidBST(TreeNode* root, TreeNode* left=NULL, TreeNode* right=NULL) {
        if (!root) {
            return true;
        }
        if (left && left->val >= root->val) {
            return false;
        }
        if (right && right->val <= root->val) {
            return false;
        }
        return isValidBST(root->left, left, root) 
                       && isValidBST(root->right, root, right);
    }
};

注意：

leetcode可以修改默认函数的声明。但是不能任意修改。只能追加带有默认值的参数。其实不难理解…… 有这个技巧。很多递归题目，递归函数参数不匹配的时候，都不需要再定义单独的递归函数啦！！！

错误解法

介绍一个错误解法：

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (!root) {
            return true;
        }
        if (root->left && root->left->val >= root->val) {
            return false;
        }
        if (root->right && root->right->val <= root->val) {
            return false;
        }
        return isValidBST(root->left) && isValidBST(root->right);
    }
};

这种错误解法，判断 示例2 会为true！

guodongxiaren commented 4 years ago

递归解法讲解

整体思路是层次向下递归判断。不符合要求就直接返回false。我们可以先不把5看成根节点，我们深入左子树，走到了1节点。

这时候对于节点5（非根的时候）有两种可能。	情况1	情况2

对于情况二，我们其实不需要多加考虑，因为既然我们能走到判断1的地方，只要我们能判断1小于父亲5，那么1也就避让小于爷爷B。

但是对于情况一，则没有这种假设。我们能判断：

1小于父亲5
父亲5大于爷爷A

但是1和爷爷A之间的关系，仍然需要特殊判断。需要1大于爷爷A！即：1<5; 1 > A

同理。对于右子树也有对称的观点。比如我们遍历到了右子树的节点6。	情况1	情况2

对于情况2。我们能判断：

父亲4小于爷爷B
节点6大于父亲4

但是节点6是否小于爷爷B，需要额外再判断。即：6 > 4; 6 < B。

综上。所有顺拐的都不需要特殊考虑，只需要判断和父亲的关系就行。但是不完全顺拐的还有和爷爷判断一下。对于层次遍历，逻辑移交到左节点时，需要保证：左小于父，左大于左爷（爷爷）；由于右节点：右大于父，右小于右爷（姥爷）

为了区分，我们把左爷叫做爷爷，把右爷叫做姥爷。所以应该有：isValidBST(root, left, right, parent) 增加的两个参数left和right分别表示爷爷和姥爷！parent表示父亲。但是由于顺拐关系的存在。所以：

对于左节点，判断了父亲，就无需再判断姥爷，只需要再判断爷爷。
对于右节点，判断了父亲，就无需再判断爷爷，只需要再判断姥爷。

isValidBST(X, Y, Z) 内部保证：

X > Y
X < Z

不管是左节点还是右节点，都是传入第一个参数X。区别在于Y和Z如何保证。回看口诀：

左小于父，左大于爷爷（左大于爷，左小于父）
右大于父，右小于姥爷

isValidBST(root->left, left, root) 
                       && isValidBST(root->right, root, right);

guodongxiaren / OJ