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账号...