题目描述:
输入一棵二叉树,判断该二叉树是否是平衡二叉树。
分析:平衡二叉树(Self-balancing binary search tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树,同时,平衡二叉树必定是二叉搜索树,反之则不一定。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。
根据定义两个子树的高度差的绝对值不超过1,那么可以通过递归求出左右子树的高度,计算它们的高度差,如果有高度差超过1,那么该树就不是平衡二叉树。
代码:1 class Solution { 2 public: 3 int isBalanced = true; 4 bool IsBalanced_Solution(TreeNode* pRoot) { 5 TreeDepth(pRoot); 6 return isBalanced; 7 } 8 9 int TreeDepth(TreeNode* pRoot) {10 if(pRoot == NULL) return 0;11 int leftTreeDepth = TreeDepth(pRoot->left);12 int rightTreeDepth = TreeDepth(pRoot->right);13 if(abs(leftTreeDepth - rightTreeDepth) > 1)14 isBalanced = false;15 return max(leftTreeDepth + 1, rightTreeDepth + 1);16 }17 };