Leetcode基础刷题之PHP解析( 98. Validate Binary Search Tree)

栏目: PHP · 发布时间: 5年前

2 0 1 9 -5 -4   期六    

Leetcode基础刷题之 PHP 解析( 144. 145)

检验一个树是不是二叉查找树

Leetcode基础刷题之PHP解析( 98. Validate Binary Search Tree)

思路有两种,二叉查找树的特点就是左子树上的结点都小于根结点,右子树上的结点都大于根节点。所以有两个方向,可以分别递归的判断左子树,右子树。或者拿左子树上的最大值,右子树上的最小值分别对应根结点进行判断。

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {

    /**
     * @param TreeNode $root
     * @return Boolean
     */
    function isValidBST($root) {
       return $this->helper($root,null,null);
    }
    
    function helper($root,$lower,$upper){
        if($root==null) return true;
        $res=$root->val;
        if($lower !==null && $res<=$lower) return false;
        if($upper !==null && $res>=$upper) return false;
        if(!$this->helper($root->left,$lower,$res)) return false;
        if(!$this->helper($root->right,$res,$upper)) return false;
        return true;
    }
}

Github整理地址:https://github.com/wuqinqiang/leetcode-php


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

The Art and Science of CSS

The Art and Science of CSS

Jonathan Snooks、Steve Smith、Jina Bolton、Cameron Adams、David Johnson / SitePoint / March 9, 2007 / $39.95

Want to take your CSS designs to the next level? will show you how to create dozens of CSS-based Website components. You'll discover how to: # Format calendars, menus and table of contents usin......一起来看看 《The Art and Science of CSS》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

随机密码生成器
随机密码生成器

多种字符组合密码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具