LeetCode OJ:Balanced Binary Tree(平衡二叉树)

LeetCode OJ:Balanced Binary Tree(平衡二叉树)

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

就是去查看一棵树是不是平衡的,一开始对平衡二叉树的理解有错误,所以写错了 ,看了别人的解答之后更正过来了:

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     bool isBalanced(TreeNode* root) {
13         int dep;
14         checkBalance(root, dep);
15     }
16     bool checkBalance(TreeNode * root, int &dep)
17     {
18         if(root == NULL){
19             dep = 0;
20             return true;
21         }
22         int leftDep, rightDep;
23         bool isLeftBal = checkBalance(root->left, leftDep);
24         bool isRightBal = checkBalance(root->right, rightDep);
25 
26         dep = max(leftDep, rightDep) + 1;
27         return isLeftBal && isRightBal && (abs(leftDep - rightDep) <= 1);
28     }
29 };

pS:感觉这个不应该easy的题目啊  想的时候头还挺疼的。。

用java的时候用上面的方法去做总是无法成功,所以换了一种方法,这个一开始没有想到,是看别人写的,代码如下所示:

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 public class Solution {
11     public boolean isBalanced(TreeNode root) {
12         if(root == null)
13             return true; 
14         if(root.left == null && root.right == null)
15             return true;
16         if(Math.abs(getDep(root.left) - getDep(root.right)) > 1)
17             return false;
18         return isBalanced(root.left) && isBalanced(root.right);
19     }
20     
21     
22     public int getDep(TreeNode node){
23         if(node == null)
24             return 0;
25         else
26             return 1 + Math.max(getDep(node.left), getDep(node.right));
27     }
28 }

 

转载于:https://www.cnblogs.com/-wang-cheng/p/4891070.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/109291.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 【重点】kubernetes 排错办法(修改k8s配置,修改docker container)

    【重点】kubernetes 排错办法(修改k8s配置,修改docker container)

  • 安卓root权限管理_root权限在哪里设置

    安卓root权限管理_root权限在哪里设置Android权限说明Android系统是运行在Linux内核上的,Android与Linux分别有自己的一套严格的安全及权限机制,Android系统权限相关的内容,(一)linux文件系统上的权限-rwxr-x–xsystemsystem41562012-06-3016:12test.apk.代表的是相应的用户/用户组及其他人对此文件的访问权限,与此文件运行起来

    2022年10月29日
  • [RK3288][Android6.0] DVP接口摄像头OV5640添加

    [RK3288][Android6.0] DVP接口摄像头OV5640添加Platform:RK3288OS:Android6.0Kernel:3.10.92DVP或者MIPI接口直接在cameraboard文件中改动就可以。cam_board_rk3288.xml:<?xmlversion=”1.0″?><BoardFile> <BoardXmlVersionversion=”v0.0xf.0″>…

  • linux配置pip源_配置国内PIP源方法

    linux配置pip源_配置国内PIP源方法python开发者都知道,当我们pipinstall安装扩展库的时候,经常遇到安装失败(超时)等,有时候是因为国外镜像被屏蔽了,带来不少麻烦,随着国内python开发的增多,越来越多企业都开放了自己的pip源:#阿里云http://mirrors.aliyun.com/pypi/simple/#中国科技大学https://pypi.mirrors.ustc.edu.cn/simple/#豆瓣…

  • uniapp 真机调试_app调试

    uniapp 真机调试_app调试一:华为手机实时调试APP代码基座流程1.打开手机的开发者模式,允许USB调试,手机操作流程,进入设置-关于手机,长按版本号(开启开发模式),然后按图操作,下拉屏幕发行已连接USB调试,手机端就暂时不用再操作了2.电脑安装360手机助手,这个软件打开浏览器或者用360软件助手下载就好了,它是HBuildX和手机连接的桥梁3.HBuildX操作运行之后就可以在控制台查看进展,会自动在手机安装APK调试基座(用于调试的APK,APK就是安卓APP的安装包).

  • 简述vue和jquery的区别「建议收藏」

    简述vue和jquery的区别「建议收藏」⾸先呢jquery他是⽤js封装的⼀个类库,主要是为了⽅便操作dom元素,⽽vue他是⼀个框架,并且呢,他会从真实dom构建出⼀个虚拟的dom树,通过di!算法渲染只发⽣改变的dom元素,其他的相同的dom元素不⽤在重新渲染.⽽使⽤jquery去改变dom元素的时候,即使有相同的dom元素也会重新渲染,jq重点操作dom,而vue重点操作数据;简单的来说就是:jquery是通过使用选择器($)选取dom对象,进行dom对象的操作,实现数据操作;它

    2022年10月16日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号