算法练习之将有序数组转换为二叉搜索树,平衡二叉树详解编程语言
2023-06-13 09:11:53 时间
1.将有序数组转换为二叉搜索树
将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。
题中,高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例: 给定有序数组: [-10,-3,0,5,9], 一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树: / / -3 9 / / -10 5
java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } class Solution { public TreeNode sortedArrayToBST(int[] nums) { return nums==null?null:buildTree(nums,0,nums.length-1); public TreeNode buildTree(int[] nums,int l,int r){ if(l r) return null; int m = l+(r-l)/2; TreeNode root = new TreeNode(nums[m]); root.left = buildTree(nums,l,m-1); root.right = buildTree(nums,m+1,r); return root; }
php
/** * 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 Integer[] $nums * @return TreeNode function sortedArrayToBST($nums) { return empty($nums)?null:$this- buildTree($nums,0,count($nums)-1); function buildTree($nums,$l,$r){ if($l $r) return null; $m = $l+(int)(($r-$l)/2); $root = new TreeNode($nums[$m]); $root- left = $this- buildTree($nums,$l,$m-1); $root- right = $this- buildTree($nums,$m+1,$r); return $root; }
2.平衡二叉树
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1
示例 1: 给定二叉树 [3,9,20,null,null,15,7] / / 9 20 / / 15 7 返回 true 示例 2: 给定二叉树 [1,2,2,3,3,null,null,4,4] / / 2 2 / / 3 3 / / 4 4 返回 false
java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } class Solution { public boolean isBalanced(TreeNode root) { if(maxDepth(root) 2) return true; if(Math.abs(maxDepth(root.left)-maxDepth(root.right)) 1){ return false; }else{ return isBalanced(root.left) isBalanced(root.right); public int maxDepth(TreeNode root) { return root==null?0:Math.max(maxDepth(root.left),maxDepth(root.right))+1; }
php
/** * 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 isBalanced($root) { if($this- maxDepth($root) 2) return true; if(abs($this- maxDepth($root- left)-$this- maxDepth($root- right)) 1){ return false; }else{ return $this- isBalanced($root- left) $this- isBalanced($root- right); function maxDepth($root){ return $root==null?0:max($this- maxDepth($root- left),$this- maxDepth($root- right))+1; }
原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/20356.html
cjavaphp相关文章
- 原码补码相互转换[通俗易懂]
- YYModel高性能 iOS数据模型转换
- Permute 3 for mac(图片音视频格式转换)
- SQL开发知识:Oracle全角数字如何转换半角数字
- Linux下文本格式转换的简易指南(linux文本格式)
- java日期格式转换大全详解编程语言
- MySQL中将int类型转换为其他类型(mysql转换int)
- 解读Oracle编码转换,优化数据库存储效率(oracle编码转换)
- 解决Oracle中时间戳转换的困境(oracle中时间戳转换)
- MSSQL中的转换字符串函数实践(mssql 转字符串函数)
- mssql中文编码转换技术实践(mssql 编码转中文)
- Redis中数据批量转换为JSON格式(redis 转json)
- C#生转换网页为pdf
- JavaScript转换农历类实现及调用方法
- Javascript的时间戳和php的时间戳转换注意事项
- 深入解析phpCB批量转换的代码示例
- php将access数据库转换到mysql数据库的方法