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


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

查看所有标签

猜你喜欢:

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

数据结构C++语言描述

数据结构C++语言描述

William Ford,William Topp / 刘卫东 沈官林 / 清华大学出版社 / 1999-09-01 / 58.00

一起来看看 《数据结构C++语言描述》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

SHA 加密
SHA 加密

SHA 加密工具

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具