By

文章目录
  1. 1. Validate Binary Search Tree
    1. 1.1. 题目
    2. 1.2. 思路
    3. 1.3. 解题

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.

思路

中序遍历

解题

c++版

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
/**
 * 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:
    vector<int> num;
    bool isValidBST(TreeNode* root) {
        inorder(root);
        for(int i=1;i<num.size();i++){
            if(num[i]<=num[i-1])
                return false;
        }
        return true;
    }
    void inorder(TreeNode *root){
        if(root){
            inorder(root->left);
            num.push_back(root->val);
            inorder(root->right);
        }
    }
};

python版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param {TreeNode} root
    # @return {boolean}
    def isValidBST(self, root):
        num=[]
        self.inorder(root,num)
        for i in range(1,len(num)):
            if num[i]<=num[i-1]:
                return False
        return True
    
    def inorder(self,root,num):
        if root:
            self.inorder(root.left,num)
            num.append(root.val)
            self.inorder(root.right,num)

c++ 节省空间版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 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:
    TreeNode *pre=NULL;
    bool isValidBST(TreeNode* root) {
        if(root!=NULL){
            if(!isValidBST(root->left)) return false;
            if(pre!=NULL && root->val<=pre->val) return false;
            pre=root;
            return isValidBST(root->right);
        }
        return true;
    }
};
leetcode
leetcode,tree
文章目录
  1. 1. Validate Binary Search Tree
    1. 1.1. 题目
    2. 1.2. 思路
    3. 1.3. 解题