[C++]LeetCode: 122 Validate Binary Search Tree (是不是是合法BST树)

[C++]LeetCode: 122 Validate Binary Search Tree (是否是合法BST树)

题目：

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.

Answer 1: 上下界法

思路：根据题目中的设定，我们对于每一个结点都保存它的上下界，也就是保证结点满足它的左子树的每个结点都比当前结点值小，右子树的每个结点都比当前结点值大。对于根结点不用定上下界，我们设置无穷小和无穷大，接下来当我们往左子树走时，上界就变成当前结点的值，下界不变。往右子树走时，下界变成当前节点值，上界不变。如果遇到递归中的结点值超越了自己的上下界，返回false，否则返回左右子树的结果。注意，空子树和只有一个结点的子树，都是BST树。还有无穷大和无穷小量的选择，INT_MIN和INT_MAX, 无法满足有些特殊结点值的需求，比如{2147483647}，超出了整数的范围，需要用LONG_MAX和LONG_MIN解决。

Attention:

1. 我们需要满足左子树的所有节点都小于根结点的值，右子树的所有节点都大于根结点的值，所以需要保存上下限。

2. 考虑到特殊的情况，我们需要扩大无穷大和无穷小的范围。

return isValidBST_helper(root, LONG_MIN, LONG_MAX);

 bool isValidBST_helper(TreeNode* root, long min, long max)

3. 空子树和只有一个节点的树都是BST.
复杂度：对树做一次遍历，时间复杂度O(N), 空间复杂度O(lg(n)).

这种做法需要考虑最大值和最小值如何设定，是和语言相关的量，不具有普遍性。

AC Code:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode *root) {
        if(root == NULL) return true;
        return isValidBST_helper(root, LONG_MIN, LONG_MAX);
    }

private:
    bool isValidBST_helper(TreeNode* root, long min, long max)
    {
        if(root == NULL)
            return true;
        
        if(root->val <= min || root->val >= max) return false;
        return isValidBST_helper(root->left, min, root->val) && isValidBST_helper(root->right, root->val, max);
    }
};

Answer 2: 中序遍历法

思路：我们利用二分查找的性质，二分查找树的中序遍历是按照顺序递增的。所以我们只需要中序遍历一遍这棵树，维护前驱结点，每次检查是否满足递增关系即可。我们先中序遍历左孩子，直到没有左孩子，返回和前驱结点比较，然后递归这个节点的右孩子。即完成中序遍历过程。

Attention:

1. 前驱结点需要设置为引用类型，因为我们需要这个pre的值能够影响它在函数外部的值，即在各层递归中都同时改变。

bool in_order(TreeNode* node, TreeNode* &pre)

2. 注意如何实现中序遍历的，要加深理解和应用。

复杂度:O(N)

二分查找树在面试中非常常见，它既是树的结构，又带有一些特殊的性质，并且模型比较简单，很适合在面试中考察基本的数据结构和算法，所以要对二分查找树理解透彻。

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode *root) {
        TreeNode* pre = NULL;
        return in_order(root, pre);
    }

private:
    bool in_order(TreeNode* node, TreeNode* &pre)
    {
        if(node == NULL)
            return true;
        
        if(!in_order(node->left, pre)) return false;
        if(pre != NULL && pre->val >= node->val) return false;
        pre = node;
        return in_order(node->right, pre);
    }
};

[C++]LeetCode: 122 Validate Binary Search Tree (是不是是合法BST树)

相关推荐