leetCode 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;
}
}
转载链接：https://leetcode.cn/
![[爱了]](/js/img/d1.gif)
![[尴尬]](/js/img/d16.gif)