本文是力扣LeeCode-110、平衡二叉树 学习与理解过程,本文仅做学习之用,对本题感兴趣的小伙伴可以出门左拐LeeCode。
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例 1:
输入:root = [3,9,20,null,null,15,7]
输出:true
示例 2:
输入:root = [1,2,2,3,3,null,null,4,4]
输出:false
示例 3:
输入:root = []
输出:true
提示:
- 树中的节点数在范围 [0, 5000] 内
- -104 <= Node.val <= 104
整体思路
求深度
可以从上到下
去查 所以需要前序遍历(中左右)
,⽽⾼度
只能从下到上
去查,所以只能后序遍历
(左右中)
这道题既然要求⽐较⾼度,必然是要后序遍历
代码思路:
1.平衡二叉树任意节点两边的子树深度相差绝对值不会超过1,且每个子树都满足这个条件,
那我们可以对每个节点找到两边的深度。
2.再判断是否两边相差绝对值超过1。
3.然后因为每个子树都满足这个条件,我们还需要遍历二叉树每个节点当成一棵子树进行判
断,而对于每个每个节点判断后,其子节点就是子问题,因此可以用递归。
步骤:
1.IsBalanced_Solution递归遍历二叉树所有节点。
2.对于每个节点判断,调用depth()函数获取子树深度。
3.depth()函数递归获取子树深度,只需要不断往子节点深度遍历,累加左右深度的较大值。
4.根据深度判断该节点下的左右子树是否为平衡二叉树。
5.每个节点层层进行判断高度。
递归法
1、明确递归函数的参数和返回值
int depth(TreeNode node)
2、明确终⽌条件
//空树为平衡二叉树,无论是根节点,还是叶子结点的子节点都可以判断
if(root==null)return true;
3.、明确单层递归的逻辑文章来源:https://www.toymoban.com/news/detail-814358.html
int left = depth(root.left); // 左
int right = depth(root.right); // 右
//左子树深度减去右子树相差绝对值大于1
if(Math.abs(left-right)>1)return false; // 中
//同时,左右子树还必须是平衡的,只要遇到null,都会为true,
//有一个为false,都为false了
return isBalanced(root.left)&&isBalanced(root.right);
depth函数用于求传入节点为根节点这个子数的高度文章来源地址https://www.toymoban.com/news/detail-814358.html
//计算该子树深度函数
int depth(TreeNode node){
if(node==null)return 0;
int left = depth(node.left);
int right = depth(node.right);
return left>right?left+1:right+1; // 以当前节点为根节点的树的最⼤⾼度
}
整体代码
class Solution {
public boolean isBalanced(TreeNode root) {
if(root==null)return true;
int left = depth(root.left);
int right = depth(root.right);
if(Math.abs(left-right)>1)return false;
return isBalanced(root.left)&&isBalanced(root.right);
}
int depth(TreeNode node){
if(node==null)return 0;
int left = depth(node.left);
int right = depth(node.right);
return left>right?left+1:right+1;
}
}
到了这里,关于每日一练:LeeCode-110、平衡二叉树【二叉树】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!