代码随想录算法训练营第十六天 | leetcode：最大二叉树 ,合并二叉树,二叉搜索树中的搜索,验证二叉搜索树
14 / 0 / 创建于 1个月前 /
_zzh 的个人博客
654. 最大二叉树
解题方法
- 构造树一般采用的是前序遍历，因为先构造中间节点，然后递归构造左子树和右子树。
- 1 <= nums.length <= 1000，不用考虑nums为空的情况。
- 先要找到数组中最大的值和对应的下标， 最大的值构造根节点，下标用来下一步分割数组。
- 寻找数组中最大值所在的下标左区间，构造左子树
- 寻找数组中最大值所在的下标右区间，构造右子树
- array_slice裁剪结果为左闭右开。
code
递归法
class Solution {
/**
* @param Integer[] $nums
* @return TreeNode
*/
function constructMaximumBinaryTree($nums) {
return $this->traversal($nums);
}
function traversal($nums){
$tree = new TreeNode();
//判断只有一个节点的情况
if(count($nums) == 1) {
$tree->val = $nums[0];
return $tree;
}
//求最大值与其索引
$max = max($nums);
$maxIndex = array_search($max,$nums);
$tree->val = $max;
//保证左区间至少有一个数值。
if($maxIndex > 0){
//递归最大值左区间，array_slice结果为左闭右开的裁剪
$tree->left = $this->traversal(array_slice($nums,0,$maxIndex));
}
//保证右区间至少有一个数值。
if($maxIndex < count($nums) - 1){
//递归最大值右区间
$tree->right = $this->traversal(array_slice($nums,$maxIndex + 1));
}
return $tree;
}
}617. 合并二叉树
解题方法
- 要合入两个二叉树，那么参数至少是要传入两个二叉树的根节点，返回值就是合并之后二叉树的根节点。
- 重复利用root1,作为合并之后的树。
root1 的左子树是：合并 root1左子树 root2左子树之后的左子树。
root1 的右子树：是 合并 root1左子树 root2右子树之后的右子树。
code
递归法
class Solution {
/**
* @param TreeNode $root1
* @param TreeNode $root2
* @return TreeNode
*/
function mergeTrees($root1, $root2) {
//如果root1递归的节点为空，合并之后就应该是root2递归的节点
if($root1 == null) return $root2;
//如果root2递归的节点为空，合并之后就应该是root1递归的节点
if($root2 == null) return $root1;
//修改root1
$root1->val += $root2->val;
//递归合并左子树
$root1->left = $this->mergeTrees($root1->left,$root2->left);
//递归合并右子树
$root1->right = $this->mergeTrees($root1->right,$root2->right);
return $root1;
}
}700. 二叉搜索树中的搜索
解题方法
- 二叉搜索树是一个有序树：
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉搜索树
- 因为二叉搜索树的节点是有序的，所以可以有方向的去搜索。
如果root->val > val，搜索左子树，如果root->val < val，就搜索右子树，最后如果都没有搜索到，就返回NULL,搜索到就返回当前节点。
code
递归法
class Solution {
/**
* @param TreeNode $root
* @param Integer $val
* @return TreeNode
*/
function searchBST($root, $val) {
if($root == null || $root->val == $val) return $root;
$res = new TreeNode();
if($root->val > $val) $res = $this->searchBST($root->left,$val);
if($root->val < $val) $res = $this->searchBST($root->right,$val);
return $res;
}
}迭代法
class Solution {
/**
* @param TreeNode $root
* @param Integer $val
* @return TreeNode
*/
function searchBST($root, $val) {
if($root == null) return null;
while($root !== null){
if($root->val > $val){
$root = $root->left;
}elseif($root->val < $val){
$root = $root->right;
}else{
return $root;
}
}
return null;
}
}98. 验证二叉搜索树
解题方法
- 在中序遍历下，输出的二叉搜索树节点的数值是有序序列。根据这个特性，验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了。
- 二叉搜索树中不能有重复元素。
- 不能单纯的比较左节点小于中间节点，右节点大于中间节点就完事了。要比较的是左子树所有节点小于中间节点，右子树所有节点大于中间节点。
code
递归法
class Solution {
private $pre = null;
/**
* @param TreeNode $root
* @return Boolean
*/
function isValidBST($root) {
//空节点也是二叉搜索树
if($root == null) return true;
//递归左子树
$left = $this->isValidBST($root->left);
//判断前一个节点的值是否大于等于当前节点，$this->pre !== null，当前是叶子节点时，不用判断
if($this->pre !== null && $this->pre >= $root->val) return false;
//记录前一个节点
$this->pre = $root->val;
$right = $this->isValidBST($root->right);
//当左子树与右子树都为true时,整个树才是true
return $left && $right;
}
}本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号
推荐文章：