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
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/109291.html原文链接：https://javaforall.net
