LeetCode: 98. 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.

Example 1:

2
   / \
  1   3
           

Binary tree

[2,1,3]

, return

true

.

Example 2:

1
   / \
  2   3
           

Binary tree

[1,2,3]

, return

false

.

題目大意: 判斷給定二叉樹是否是 BST(二叉搜尋樹)。

解題思路

• 方法一: 由于 BST 的中序周遊是遞增序列, 是以隻需要中序列周遊，判斷是否滿足要求即可。
• 方法二: 遞歸地判斷相關子樹是否在給定的區間内(左子樹的元素都大于根節點的元素，右節點的元素都小于根節點的元素)。

AC 代碼

• 方法一:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
// 由于 BST 的中序周遊是遞增序列, 是以隻需要中序列周遊，判斷是否滿足要求即可
class Solution {
private:
    // 中序周遊
    void inOrderScan(TreeNode* root, vector<int>& inOrderSequence)
    {
        if(root == nullptr) return;

        // 中序周遊左子樹
        inOrderScan(root->left, inOrderSequence);
        // 讀取根節點
        inOrderSequence.push_back(root->val);
        // 中序周遊右子樹
        inOrderScan(root->right, inOrderSequence);
    }

    // 判斷給定序列的 [beg, end) 區間是否是遞增序列
    bool isAscendSequence(const vector<int>& inOrderSequence, int beg, int end)
    {
        if(beg+ >= end) return true;
        else if(inOrderSequence[beg] < inOrderSequence[beg+]) return isAscendSequence(inOrderSequence, beg+, end);
        else return false;
    }
public:
    bool isValidBST(TreeNode* root) {

        // root 的中序周遊序列
        vector<int> inOrderSequence;
        inOrderScan(root, inOrderSequence);

        return isAscendSequence(inOrderSequence, , inOrderSequence.size());
    }
};
           

• 方法二:

/**
 * 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 {
private:
    // 判斷給定子樹的元素是否在區間 (min, max) 中
    bool isValidBSTRef(TreeNode* root, long long min = LLONG_MIN, long long max = LLONG_MAX) {
        bool bRet = false;
        do
        {
            if(root == nullptr)
            {
                bRet = true;
                break;
            }

            if(root->val <= min || root->val >= max) break;

            // 左子樹的元素應該大于根節點的元素
            if(!isValidBSTRef(root->left, min, root->val))
            {
                break;
            }

            // 右子樹的元素應該小于根節點的元素
            if(!isValidBSTRef(root->right, root->val, max))
            {
                break;
            }

            bRet = true;
        }while(false);

        return bRet;
    }
public:
    bool isValidBST(TreeNode* root) {
        return isValidBSTRef(root);
    }
};