[leetcode] 110.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 everynode never differ by more than 1.
example 1:
given the following tree [3,9,20,null,null,15,7]:
3
/
9 20
/
15 7
return true.
example 2:
given the following tree [1,2,2,3,3,null,null,4,4]:
1
/
2 2
/
3 3
/
4 4
return false.
求二叉树是否平衡,根据题目中的定义,高度平衡二叉树是每一个结点的两个子树的深度差不能超过1,那么我们肯定需要一个求各个点深度的函数,然后对每个节点的两个子树来比较深度差,时间复杂度为o(nlgn),代码如下:
解法一:
class solution { public: bool isbalanced(treenode *root) { if (!root) return true; if (abs(getdepth(root->left) - getdepth(root->right)) > 1) return false; return isbalanced(root->left) && isbalanced(root->right); } int getdepth(treenode *root) { if (!root) return 0; return 1 + max(getdepth(root->left), getdepth(root->right)); } };
上面那个方法正确但不是很高效,因为每一个点都会被上面的点计算深度时访问一次,我们可以进行优化。方法是如果我们发现子树不平衡,则不计算具体的深度,而是直接返回-1。那么优化后的方法为:对于每一个节点,我们通过checkdepth方法递归获得左右子树的深度,如果子树是平衡的,则返回真实的深度,若不平衡,直接返回-1,此方法时间复杂度o(n),空间复杂度o(h),参见代码如下:
解法二:
class solution { public: bool isbalanced(treenode *root) { if (checkdepth(root) == -1) return false; else return true; } int checkdepth(treenode *root) { if (!root) return 0; int left = checkdepth(root->left); if (left == -1) return -1; int right = checkdepth(root->right); if (right == -1) return -1; int diff = abs(left - right); if (diff > 1) return -1; else return 1 + max(left, right); } };
类似题目:
maximum depth of binary tree
参考资料:
https://leetcode.com/problems/balanced-binary-tree/discuss/35691/the-bottom-up-o(n)-solution-would-be-better
https://leetcode.com/problems/balanced-binary-tree/discuss/35686/java-solution-based-on-height-check-left-and-right-node-in-every-recursion-to-avoid-further-useless-search
到此这篇关于c++实现leetcode(110.平衡二叉树)的文章就介绍到这了,更多相关c++实现平衡二叉树内容请搜索<计算机技术网(www.ctvol.com)!!>以前的文章或继续浏览下面的相关文章希望大家以后多多支持<计算机技术网(www.ctvol.com)!!>!
需要了解更多c/c++开发分享C++实现LeetCode(110.平衡二叉树),都可以关注C/C++技术分享栏目—计算机技术网(www.ctvol.com)!
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/676269.html