扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
题目:输入一棵二叉树的根结点,判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。
目前成都创新互联已为数千家的企业提供了网站建设、域名、虚拟主机、网站托管、服务器租用、企业网站设计、镇坪网站维护等服务,公司将坚持客户导向、应用为本的策略,正道将秉承"和谐、参与、激情"的文化,与客户和合作伙伴齐心协力一起成长,共同发展。有了求二叉树的深度的经验之后再解决这个问题,我们很容易就能想到一个思路:在遍历树的每个结点的时候,调用函数TreeDepth得到它的左右子树的深度。如果每个结点的左右子树的深度相差都不超过1,按照定义它就是一棵平衡的二叉树。这种思路对应的代码如下:
bool IsBalanced(BinaryTreeNode* pRoot) { if(pRoot == NULL) return true; int left = TreeDepth(pRoot->m_pLeft); int right = TreeDepth(pRoot->m_pRight); int diff = left - right; if(diff > 1 || diff < -1) return false; return IsBalanced(pRoot->m_pLeft) && IsBalanced(pRoot->m_pRight); }
上面的代码固然简洁,但我们也要注意到由于一个节点会被重复遍历多次,这种思路的时间效率不高。例如在函数IsBalance中输入上图中的二叉树,首先判断根结点(值为1的结点)的左右子树是不是平衡结点。此时我们将往函数TreeDepth输入左子树根结点(值为2的结点),需要遍历结点4、5、7。接下来判断以值为2的结点为根结点的子树是不是平衡树的时候,仍然会遍历结点4、5、7。毫无疑问,重复遍历同一个结点会影响性能。接下来我们寻找不需要重复遍历的算法。
如果我们用后序遍历的方式遍历二叉树的每一个结点,在遍历到一个结点之前我们已经遍历了它的左右子树。只要在遍历每个结点的时候记录它的深度(某一结点的深度等于它到叶节点的路径的长度),我们就可以一边遍历一边判断每个结点是不是平衡的。
#include#include using namespace std; struct BinaryTreeNode { int data; BinaryTreeNode* left; BinaryTreeNode* right; BinaryTreeNode(int x) :data(x) , left(NULL) , right(NULL) {} }; class BinaryTree { protected: BinaryTreeNode* _root; BinaryTreeNode* _CreateBinaryTree(int* arr, int& index, int size) { BinaryTreeNode* root = NULL; if (index < size&&arr[index] != '#') { root = new BinaryTreeNode(arr[index]); root->left = _CreateBinaryTree(arr, ++index, size); root->right = _CreateBinaryTree(arr, ++index, size); } return root; } public: BinaryTree() :_root(NULL) {} BinaryTree(int *arr, int size) { int index = 0; _root = _CreateBinaryTree(arr, index, size); } bool IsBalance() { int depth = 0; return _IsBalance(_root, depth); } int Height() { return _Height(_root); } void PreOrder_Non() { if (_root == NULL) return; BinaryTreeNode* cur = _root; stack s; s.push(_root); while (!s.empty()) { cur = s.top(); printf("%d ", cur->data); s.pop(); if (cur->right) s.push(cur->right); if (cur->left) s.push(cur->left); } cout << endl; } protected: int _Height(BinaryTreeNode* root) { if (root == NULL) return 0; int left = _Height(root->left); int right = _Height(root->right); return left > right ? left + 1 : right + 1; } bool _IsBalance(BinaryTreeNode* root, int& depth) { if (root == NULL) return true; int left, right; if (_IsBalance(root->left, left) && _IsBalance(root->right, right)) { int dif = left - right; if (dif <= 1 && dif >= -1) { depth = left > right ? left + 1 : right + 1; return true; } } return false; } }; int main() { int a[] = { 1,2,3,'#','#','#'}; BinaryTree t(a,sizeof(a)/sizeof(a[0])); t.PreOrder_Non(); cout< 在上面的代码中,我们用后序遍历的方式遍历整棵二叉树。在遍历某结点的左右子结点之后,我们可以根据它的左右子结点的深度判断它是不是平衡的,并得到当前结点的深度。当最后遍历到树的根结点的时候,也就判断了整棵二叉树是不是平衡二叉树了。
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
网页名称:后序遍历求解判断一颗二叉树是否为平衡二叉树-创新互联
浏览地址:http://kswjz.com/article/csopdh.html
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流