首页 > 其他分享 >98. Validate Binary Search Tree

98. Validate Binary Search Tree

时间:2022-11-19 18:22:10浏览次数:40  
标签:TreeNode helper Tree tn 98 return Validate null root

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.
Solution 1: //相当于中序遍历,先加入中间节点,再加入左节点,再加入右节点 class Solution {     public boolean isValidBST(TreeNode root) {         if (root == null)             return true;         Stack<TreeNode> s = new Stack<>();         TreeNode pre = null;         s.push(root);         while (!s.isEmpty()) {             TreeNode tn = s.peek();             while (tn != null) {                 tn = tn.left;                                 s.push(tn);                                         }             s.pop();             if (!s.isEmpty()) {                 tn = s.pop();                 if (pre != null && tn.val <= pre.val)                    return false;                 pre = tn;                             s.push(tn.right);             }                     }         return true;     } }   Solution 2://必须是Long类型,例如只有有个2^31-1节点,如果把Long改成Integer,则会报错 class Solution {     Integer prev = null;     boolean isValid = true;     public boolean isValidBST(TreeNode root) {         helper(root);         return isValid;     }          private void helper(TreeNode root) {         if (root == null)             return;         if (isValid == false)             return;         helper(root.left);         if (prev != null) {             if (root.val <= prev)                 isValid = false;         }         prev = root.val;         helper(root.right);                    } }

标签:TreeNode,helper,Tree,tn,98,return,Validate,null,root
From: https://www.cnblogs.com/MarkLeeBYR/p/16906689.html

相关文章

  • 98:私有属性
    Python对于类的成员没有严格的访问控制限制,这与其他面向对象语言有区别。关于私有属性和私有方法,有如下要点:1.通常我们约定,两个下划线开头的属性是私有的(private)。其他......
  • js树形组件zTree简单使用
    <!DOCTYPEhtml><html><head><title>ZTREEDEMO</title><metahttp-equiv="content-type"content="text/html;charset=UTF-8"/><linkrel="stylesh......
  • 1102 Invert a Binary Tree
    ThefollowingisfromMaxHowell@twitter:Google:90%ofourengineersusethesoftwareyouwrote(Homebrew),butyoucan'tinvertabinarytreeonawhiteboa......
  • elementUI tree树节点文字超出时省略或折行 样式
    文字超出时折行::v-deep.tree{width:100%;.el-tree-node{white-space:normal;.el-tree-node__content{height:100%;a......
  • 代码48985656
    4564jashdahdoias的款式哦对哈送i和x下面是演示代码//这里是需要高亮的代码importReact,{Component}from'react'componentDidCat......
  • @Validated与@Valid的区别
    @Validated可以配合分组使用,如QueryGroup.class,就只校验加了QueryGroup.class的属性@Valid只具备基础功能,并不具备分组校验的功能@ApiOperation("查询动态跟踪分页")......
  • TreeUtils工具类一行代码实现列表转树 实战Java8 三级菜单 三级分类 附视频
    一、序言在日常一线开发过程中,总有列表转树的需求,几乎是项目的标配,比方说做多级菜单、多级目录、多级分类等,有没有一种通用且跨项目的解决方式呢?帮助广大技术朋友给业务瘦......
  • Codeforces 1646 D. Weight the Tree
    题意给你n个节点的树,让你给每个节点进行赋值,并且赋的值需要为正整数;同时当一个节点的值等于所有邻居节点的值的和时,这个点为好点;求出一组赋值情况,满足树的好点个数最大......
  • el-tree 初始加载中状态
    问题二次封装了一个el-tree组件MenuTree,想要在树形数据nodeData传递之前,树显示为loading加载中的状态。原代码是在MenuTree中监听nodeData,data中声明treeLo......
  • el-tree 的 setCheckedKeys() 无效
    问题打开对话框时,加载里面的树,并且勾选默认节点。在对话框中监听dialogOpen为true时就调用el-tree的setCheckedKeys()方法。但是总是报错无法读取树。试过$next......