剑指 Offer 55 - II. 平衡二叉树(leetcode每日打卡)
2021/11/11 23:10:20
本文主要是介绍剑指 Offer 55 - II. 平衡二叉树(leetcode每日打卡),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录
题目描述
思路
题解
题目描述
输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4
思路
此树的深度 等于 左子树的深度 与 右子树的深度 中的 最大值 +1 。
后序遍历 + 剪枝 (从底至顶)
题解
/** * 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) { int res=recur(root); if(res!=-1){ return true; } return false; } public int recur(TreeNode node){ if(node==null){ return 0; } int left=recur(node.left); if(left==-1){ return -1; } int right=recur(node.right); if(right==-1){ return -1; } if(Math.abs(left-right)<2){ return Math.max(left,right)+1; }else{ return -1; } } }
执行结果:
通过
显示详情
添加备注
执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗:38.5 MB, 在所有 Java 提交中击败了28.65%的用户
通过测试用例:227 / 227
这篇关于剑指 Offer 55 - II. 平衡二叉树(leetcode每日打卡)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-20whatsapp webhook 回调的签名验证偶尔会失败是什么原因-icode9专业技术文章分享
- 2024-09-19Excel数据导出课程:初学者必备教程
- 2024-09-19Excel数据导入课程:新手入门指南
- 2024-09-19RBAC的权限管理入门教程
- 2024-09-19如何使用Svg Sprite Icon制作图标
- 2024-09-19uniapp 如何实现点赞后全局更新数据-icode9专业技术文章分享
- 2024-09-19云函数怎么运行wx-server-sdk-icode9专业技术文章分享
- 2024-09-19"dependencies": { "wx-server-sdk": "latest" },是什么意思-icode9专业技术文章分享
- 2024-09-16优化批处理流程:自定义BatchProcessorUtils的设计与应用
- 2024-09-15laravel collect游标批量插入的方法示例-icode9专业技术文章分享