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)


相关推荐

发表回复

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

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