`

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.

   解题思路 : 利用BST中序遍历是排好序的!

   第一次做的时候思路错了,以为只要遍历的时候,加一个条件判断是否左右节点满足条件!

   那样的话,就可能存在根节点的右边小于它的节点或左边大于他的节点;

 

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isValidBST(TreeNode root) {
        List<Integer> nodes = new ArrayList<Integer> ();
        return validateBST(root,nodes);
    }
    
    boolean validateBST(TreeNode root,List<Integer> nodes ) {
        if (root == null) return true;
        if (!validateBST(root.left,nodes))
            return false;
        int val = root.val;
        if (nodes.isEmpty()) nodes.add(val);
        else if (nodes.get(nodes.size() - 1) >= val) {
            return false;
        } {
            nodes.add(val);
        }
        if (!validateBST(root.right,nodes))
            return false;
        return true;
    }
}

 

分享到:
评论

相关推荐

    python-leetcode题解之098-Validate-Binary-Search-Tree

    python python_leetcode题解之098_Validate_Binary_Search_Tree

    js-leetcode题解之98-validate-binary-search-tree.js

    js js_leetcode题解之98-validate-binary-search-tree.js

    c语言-leetcode题解之0098-validate-binary-search-tree.zip

    c语言基础 c语言_leetcode题解之0098_validate_binary_search_tree.zip

    javalruleetcode-what_the_dead_men_say:what_the_dead_men_say

    Validate Binary Search Tree - Java Recursive - Java Iterative - Java Inorder 0099 Recover Binary Search Tree - Java Recursive 0101 Symmetric tree - Java Recursive - Java Iterative - C Recursive...

    算法面试通关40讲完整课件 18-20 树、二叉树、二叉搜索树

    1. **验证二叉搜索树 (Validate Binary Search Tree)**:给定一个二叉树,判断它是否是有效的二叉搜索树。 2. **二叉搜索树的最近公共祖先 (Lowest Common Ancestor of a Binary Search Tree)**:在二叉搜索树中找到...

    LeetCode 精选 TOP 面试题(3)1

    Validate Binary Search Tree)和判断对称二叉树(101. Symmetric Tree)。这两个问题都涉及到对二叉树结构的深入理解和遍历策略。 首先,我们来看验证二叉搜索树。二叉搜索树(Binary Search Tree, BST)是一种...

    Leetcode题目+解析+思路+答案.pdf

    - **Validate Binary Search Tree**:验证一个二叉树是否为二叉搜索树。 - **Recover Binary Search Tree**:恢复二叉搜索树中的两个错误节点。 - **Binary Tree Path**:找到二叉树中和为目标值的路径。 - **...

    常见算法题答案及解析

    25. Validate Binary Search Tree:验证二叉搜索树的合法性。 26. Maximum Depth of Binary Tree:二叉树的最大深度。 27. Minimum Depth of Binary Tree:二叉树的最小深度。 28. Balanced Binary Tree:判断二叉树...

    python-leetcode面试题解之第98题验证二叉搜索树-题解.zip

    本压缩包文件“python-leetcode面试题解之第98题验证二叉搜索树-题解.zip”专注于解决LeetCode的第98题,即“验证二叉搜索树”(Validate Binary Search Tree)。下面我们将深入探讨这个话题,了解如何使用Python来...

    Leetcode book刷题必备

    25. Validate Binary Search Tree:验证二叉搜索树。 26. Maximum Depth of Binary Tree:计算二叉树的最大深度。 27. Minimum Depth of Binary Tree:计算二叉树的最小深度。 28. Balanced Binary Tree:判断一个...

    CleanCodeHandbook_v1.0.3

    - Validate Binary Search Tree(验证二叉搜索树) - Maximum Depth of Binary Tree(二叉树的最大深度) - Convert Sorted Array to Binary Search Tree(将有序数组转换为二叉搜索树) 7. Bit Manipulation...

    Leetcode的ac是什么意思-LeetCodeInJava:leetcode-java

    Validate Binary Search Tree #100 Same Tree #104 Maximum Depth of Binary Tree #122 Best Time to Buy and Sell Stock II #136 Single Number #150 Evaluate Reverse Polish Notation #169 Majority Element #171...

    手稿_V1.031

    5. **验证二叉搜索树的有效性** (Validate Binary Search Tree) - 验证一个二叉树是否是二叉搜索树,可以通过中序遍历后检查序列是否严格升序来实现。 - 示例代码中,使用迭代中序遍历,在遍历过程中维护一个栈,...

    php-leetcode题解之验证二叉搜索树.zip

    在本压缩包“php-leetcode题解之验证二叉搜索树.zip”中,主要包含的是使用PHP语言解决LeetCode上的一道题目——验证二叉搜索树(Validate Binary Search Tree)。LeetCode是一个流行的在线编程挑战平台,它提供了...

    leetcode java

    - 例如,验证二叉搜索树(Validate Binary Search Tree)需要判断给定的二叉树是否符合二叉搜索树的定义。 - 计算二叉树的最大深度(Maximum Depth of Binary Tree)考察递归的使用。 - 平衡二叉树(Balanced Binary...

    LeetCode最全代码

    * [Binary Search Tree](https://github.com/kamyu104/LeetCode#binary-search-tree) * [Breadth-First Search](https://github.com/kamyu104/LeetCode#breadth-first-search) * [Depth-First Search]...

    LeetCode各公司题目合集

    - Validate Binary Search Tree:验证给定的二叉树是否为有效的二叉搜索树(BST),这需要对二叉树的遍历和树节点值的区间限制有清晰的理解。 - Valid Parentheses:这是一个用来检测字符串中括号是否有效匹配的问题...

    leetcode跳跃-leetcode:leetcode一天一次

    leetcode ...Validate Binary Search Tree - 二分查找 二分查找 + 数据缓存:1095. Find in Mountain Array 链表 有序链表合并:21. Merge Two Sorted Lists 回文 双指针判断回文:680. 验证回文字符串 Ⅱ

    LeetCode:LeetCode上一些算法的解答

    5. **二叉树**:二叉树问题包括遍历、查找、平衡调整等,如"二叉树的最大路径和"(Maximum Path Sum)、"验证二叉搜索树"(Validate Binary Search Tree)。 6. **回溯**:回溯是一种尝试所有可能解的算法策略,...

Global site tag (gtag.js) - Google Analytics