判断一棵树是否是平衡二叉树及其时间复杂度的优化 |
您所在的位置：网站首页 › 树遍历时间复杂度 › 判断一棵树是否是平衡二叉树及其时间复杂度的优化 |
|
平衡二叉树：它是一棵空树或者左右子树的高度差绝对值不超过1，并且左右两棵子树都是平衡二叉树。 要判断一棵树是否是平衡二叉树，由其定义我们很容易想到通过计算出左右两棵子树的高度及其高度差来进行判断。 首先，判断当前节点是否是平衡二叉树，则需要开始遍历整棵树，求其左右子树的高度。递归判断其左右子树是否为平衡二叉树，又一次需要遍历其子树求其高度。多次求其高度，越接近叶子节点的节点高度被求的次数越多。 这种方法很容易理解，但是它的时间复杂度是O(N*N)，这是一种十分低效的算法。 既然导致低效的原因是因为多次求了节点的高度，因此，考虑将高度放在参数列表中，在递归的过程中返回给上一层。 也就是说，从叶子节点开始判断这棵树是否是平衡二叉树。 时间复杂度是O（N） 代码： #include using namespace std; struct Node { int _data; Node* _left; Node* _right; Node(const int& x) : _data(x) , _left(NULL) , _right(NULL) {} }; size_t Depth(Node* root) { if (root == NULL) return 0; size_t left = Depth(root->_left); size_t right = Depth(root->_right); return left > right ? left + 1 : right + 1; } //bool IsBalanceN(Node* root) //{//O(n*n) // if (root == NULL) // return true; // int leftDepth = Depth(root->_left); // int rightDepth = Depth(root->_right); // return abs(leftDepth - rightDepth) < 2 && IsBalance(root->_left) && IsBalance(root->_right); //} //时间复杂度为O(N) bool _IsBalance(Node* root, int& depth){ if (root == NULL) { depth = 0; return true; } int ldepth = 0, rdepth = 0; if (_IsBalance(root->_left, ldepth) == false) { return false; } if (_IsBalance(root->_right, rdepth) == false) { return false; } if (abs(ldepth - rdepth) > 1) { return false; } depth = ldepth > rdepth ? ldepth + 1 : rdepth + 1;//这棵子树已经是平衡二叉树了 return true;} int main() { Node* p1 = new Node(1); Node* p2 = new Node(1); Node* p3 = new Node(1); Node* p4 = new Node(1); Node* p5 = new Node(1); p1->_left = p2; p1->_right = p3; p2->_left = p4; p2->_right = p5; cout |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |