美文网首页数据结构与算法
Leetcode 98 验证二叉搜索树

Leetcode 98 验证二叉搜索树

作者: itbird01 | 来源:发表于2021-12-21 07:24 被阅读0次

98. 验证二叉搜索树

题意:给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

解题思路

解法1:
1.二叉搜索树的一个特性,是中序遍历的结果,一定为升序序列
2.根据上面的特性,遍历二叉树,判断list是否为升序

解题遇到的问题

后续需要总结学习的知识点

需要深入总结学习二叉搜索树的数据结构的特点、应用、搜索、插入、删除

##解法1
import java.util.LinkedList;

class Solution {
    LinkedList<Integer> list = new LinkedList<Integer>();
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return false;
        }

        midTree(root);
        boolean ans = true;
        int pre = list.get(0);
        for (int i = 1; i < list.size(); i++) {
            if (pre >= list.get(i)) {
                ans = false;
                break;
            } else {
                pre = list.get(i);
            }
        }
        return ans;
    }

    private void midTree(TreeNode root) {
        if (root == null) {
            return;
        }

        midTree(root.left);
        list.add(root.val);
        midTree(root.right);
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {
        }
        TreeNode(int val) {
            this.val = val;
        }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}

相关文章

网友评论

    本文标题:Leetcode 98 验证二叉搜索树

    本文链接:https://www.haomeiwen.com/subject/lrlzfrtx.html