LintCode 验证二叉查找树题目分析代码

题目

给定一个二叉树,判断它是否是合法的二叉查找树(BST)

一棵BST定义为:

  • 节点的左子树中的值要严格小于该节点的值。
  • 节点的右子树中的值要严格大于该节点的值。
  • 左右子树也必须是二叉查找树。
  • 一个节点的树也是二叉查找树。

样例 一个例子:

2 / 1 4 / 3 5 上述这棵二叉树序列化为 {2,1,4,#,#,3,5}.

分析

我们可以设置上下bound,递归左右子树时,为它们设置最大值,最小值,并且不可以超过。

注意:下一层递归时,需要把本层的up 或是down继续传递下去。相当巧妙的算法。

代码

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: True if the binary tree is BST, or false
     */

    public boolean isValidBST(TreeNode root) {
        // Just use the inOrder traversal to solve the problem.
        if (root == null) {
            return true;
        }
        
        return dfs(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    private boolean dfs(TreeNode root, long min, long max) {
        if(root == null)
            return true;
        
        if(root.val <= min || root.val >= max)
            return false;
        
        return dfs(root.left, min, root.val) && dfs(root.right, root.val, max);
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏架构之路

Java 集合系列03之 ArrayList详细介绍(源码解析)和使用示例

概要 上一章,我们学习了Collection的架构。这一章开始,我们对Collection的具体实现类进行讲解;首先,讲解List,而List中ArrayLis...

2884
来自专栏编程理解

数据结构(三):二叉树遍历

前序遍历的方式,也就是对每一棵子树,按照根节点、左子树、右子树的顺序进行访问,也就是根-左-右的访问顺序。因为每一棵非空子树,又可拆分为根节点、左子树和右子树,...

1672
来自专栏desperate633

LeetCode 144. Binary Tree Preorder Traversal题目分析代码

Given a binary tree, return the preorder traversal of its nodes' values. For ex...

962
来自专栏书山有路勤为径

二叉树转链表

给定一个二叉树,将该二叉树 就地(in-place)转换为单链表。单链表中节点顺序 为二叉树前序遍历顺序。(不额外开辟存储空间) LeetCode 114. ...

712
来自专栏赵俊的Java专栏

二叉树层序遍历为二维数组

2203
来自专栏博岩Java大讲堂

Java集合--List源码

2514
来自专栏Jack-Cui

111.Minimum Depth of Binary Tree(Tree-Easy)

Given a binary tree, find its minimum depth. The minimum depth is the number of ...

2149
来自专栏Echo is learning

剑指offer04--重建二叉树

1125
来自专栏Hongten

ArrayList, LinkedList, Vector - dudu:史上最详解

ArrayList, LinkedList, Vector - dudu:史上最详解

933
来自专栏武培轩的专栏

剑指Offer-从上往下打印二叉树

题目描述 从上往下打印出二叉树的每个节点,同层节点从左至右打印。 思路 使用两个队列一个存放节点,一个存放值。先将根节点加入到队列中,然后遍历队列中的元素,遍历...

2827

扫码关注云+社区

领取腾讯云代金券