题目:输入一棵二叉树的根结点,判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过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< 在上面的代码中,我们用后序遍历的方式遍历整棵二叉树。在遍历某结点的左右子结点之后,我们可以根据它的左右子结点的深度判断它是不是平衡的,并得到当前结点的深度。当最后遍历到树的根结点的时候,也就判断了整棵二叉树是不是平衡二叉树了。
当前文章:后序遍历求解判断一颗二叉树是否为平衡二叉树
文章来源:http://njwzjz.com/article/jedccs.html