Tree1

发表于 更新于 分类于 ，

题目描述[原题链接][https://leetcode-cn.com/problems/validate-binary-search-tree/]

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

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

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

输入:
2
/ \
1 3
输出: true

示例 2:

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

算法描述

​ 分析题意可知，满足条件的树它的中序遍历是从小到大排列的，所以进行中序遍历，结果存放入Stack中，最后判断弹栈元素是否比栈顶元素大，满足继续比较，不满足返回false，当Stack为空的时候，返回true;

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    stack<int> s;
    void LCR(TreeNode* node){
        if(node!=NULL){
            LCR(node->left);
            s.push(node->val);
            LCR(node->right); 
        }
        
    }
    bool isValidBST(TreeNode* root) {
        if(root==NULL)return true;
        LCR(root);
        int t=s.top();s.pop();
        while(!s.empty()){
            if(t>s.top()){t=s.top();s.pop();}
            else return false;
        }
        return true;
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    Stack<Integer> s = new Stack<Integer>();
    
    public void LCR(TreeNode root){
        if(root==null)return ;
        LCR(root.left);
        s.push(root.val);
        LCR(root.right);
    }
    
    public boolean isValidBST(TreeNode root) {
        if(root==null)return true;
        LCR(root);
        int t=s.pop();
        while(!s.empty()){
            if(t>s.peek())t=s.pop();
            else return false;
        }
        return true;
    }
}