在深信服组期间学习了C++的使用方法，就打算通过刷Leetcode来提高自己的算法能力以及对C++的掌握能力

经典的二叉搜索树判断的问题，做之前还是百度了一下，效果贼好

Leetcode传送门

Validate Binary Search Tree [Difficulty: Medium]

题目

  • 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.
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      Input:
          2
         / \
        1   3
      Output: true


          5
         / \
        1   4
           / \
          3   6
      Output: false
      Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value
                   is 5 but its right child's value is 4.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * 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) {

    }
};

我的思路

  • 采用递归的方式，难点在于二叉搜索树要求左子树的所有节点小于根节点，右子树的所有节点大于根节点，所以单纯递归肯定不行，必须携带上层的参数。
  • 这里就有一个巧妙的方案，每次通过上层节点的值限定这个节点可取的最大最小值，就不用取递归寻找子树的最大最小值了。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    /**
     * 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) {
            if(root == NULL) return true;
            return check(root, INT_MIN, INT_MAX);
        }

        bool check(TreeNode* root, int min, int max) {
            if(root == NULL) return true;
            if(root->val == INT_MIN && root->left != NULL) return false;
            if(root->val == INT_MAX && root->right != NULL) return false;
            if(root->val < min || root->val > max) return false;
            return (check(root->left, min, root->val-1) && check(root->right, root->val+1, max));
        }
    };

参考思路

  • 利用栈对二叉树进行前序遍历
  • 标答更像是把树看作一个线性表，然后逐个比对判断其是否合乎规则
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    /**
     * 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) {
            
            if(root == NULL)
                return true;
            
            TreeNode* current = root;
            TreeNode* pre = NULL;
            
            stack<TreeNode*> order;
            
            while(current || !order.empty()) {
                while(current) {
                    order.push(current);
                    current = current->left;
                }
                current = order.top();
                order.pop();
                if(pre && pre->val >= current->val) return false;
                pre = current;
                current = current->right;
                
            }
            
            return true;
        }
    };

如何判断一棵树为二叉搜索树

五种方法判断BST