当前位置:网站首页>LeetCode-110-平衡二叉树
LeetCode-110-平衡二叉树
2022-06-11 21:23:00 【z754916067】
题目

思路
- 思路是对二叉树做先序遍历,从底至顶返回子树最大高度,若判定某子树不是平衡树则 “剪枝” ,直接向上返回。
- 如果左右高度差≥2 :则返回 -1,代表 此子树不是平衡树,然后接着向上返回 只有全都是平衡树 才会返回非-1的值
代码
public boolean isBalanced(TreeNode root) {
return recur(root) != -1;
}
//思路是对二叉树做先序遍历,从底至顶返回子树最大高度,若判定某子树不是平衡树则 “剪枝” ,直接向上返回。
private int recur(TreeNode root) {
//空指针返回0
if (root == null) return 0;
int left = recur(root.left);
if(left == -1) return -1;
int right = recur(root.right);
if(right == -1) return -1;
//如果当前节点的左右子树的高度差<2 说明在当前节点算是平衡子树
//返回以节点root为根节点的子树的最大高度,即节点 root 的左右子树中最大高度加 1
//但如果左右高度差≥2 :则返回 -1,代表 此子树不是平衡树,然后接着向上返回 只有全都是平衡树 才会返回非-1的值
return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
}
边栏推荐
- LeetCode-43-字符串相乘
- Add personal statement for go file in file template in Golan
- LeetCode-322-零钱兑换
- 【生活思考】文字与语音
- 关于斜率优化
- JS performs non empty judgment on various data types of the returned data.
- Part I physical layer
- Flutter implements the JD address selection component
- 成长的12条黄金法则
- Brain cell membrane equivalent neural network training code
猜你喜欢

ORA-04098: trigger ‘xxx. xxx‘ is invalid and failed re-validation

Release of version 5.6 of rainbow, add multiple installation methods, and optimize the topology operation experience

Solve the problem of img 5px spacing

The secret of derating - don't challenge Datasheet

LeetCode-322-零钱兑换

Only 38 years old! Zhou Chuan, a researcher of the Chinese Academy of Sciences, died unfortunately. Rao Yi sent a document to mourn: he guided me when he was still my student

Which Bluetooth headset is better within 500? Inventory of gifts for girls' Day

Software test plan

My collection of scientific research websites

Part I physical layer
随机推荐
BZOJ3189 : [Coci2011] Slika
2021牛客多校5 Double Strings
[game theory complete information static game] strategic game
第二部分 数据链路层
一步步把 SAP UI5 应用部署到 SAP BTP Kyma 运行环境中去
Using the sap ui5 cli command line tool to build and run SAP ui5 applications
My collection of scientific research websites
LeetCode-98-验证二叉搜索树
从概率论基础出发推导卡尔曼滤波
bzoj3188 Upit
如何使用 SAP Kyma 控制台手动发送 SAP Commerce Cloud Mock 应用暴露的事件
Cs144 lab0 lab1 record
Why microservices are needed
The difference between VaR and let_ The difference between let and VaR
Field queryIndexFieldnameService in xxxImpl required a single bean, but 19 were found:
How to Load Data from CSV (Data Preparation Part)
实现 TabLayout 下标与文字等长,选中字体大小改变
ASCII码对照表
RANSAC extract cylinder (matlab built-in function)
CANN编码的一些报错汇编