【Tree】判断平衡二叉树AVL

  1 /***********************************
  2 https://leetcode.com/problems/balanced-binary-tree/
  3 @date 2015.5.8
  4 @description
  5 给定一个二叉树，判断是否是平衡二叉树
  6 @tags tree, DFS
  7 
  8 平衡二叉树满足的条件：
  9 1.左右子树的高度差不大于1
 10 2.左右子树均是平衡二叉树
 11 
 12 本次解决方案提供了两种方法：
 13 Solution1.
 14 递归先分别算出左右子树的高度，再做差与1比较，如果≤1，则再判断左右子树是否为AVL
 15 
 16 Solution2.
 17 计算并返回左右子树的高度，同时可以判断左右子树是否为AVL树，
 18 这样就不需要在判断左右字数高度差不大于1之后再回去判断左右子树是否为AVL树
 19 
 20 测试函数中增加了搜索二叉树的创建 和 递归先序遍历二叉树
 21 
 22 
 23 ************************************/
 24 
 25 
 26 #include <iostream>
 27 #include <stdlib.h>
 28 
 29 using namespace std;
 30 
 31 struct TreeNode{
 32     int val;
 33     TreeNode *left;
 34     TreeNode *right;
 35     TreeNode(int x) : val(x), left(NULL), right(NULL){}
 36 };
 37 
 38 
 39 class Solution{
 40 public:
 41     bool isBalanced(TreeNode *root){
 42         // 递归
 43         if (!root) return true; // 空树也是AVL
 44         int depthLeft = maxDepth(root->left);
 45         int depthRight = maxDepth(root->right); // 算左右子树的最大深度，即为树的高度
 46         if (abs(depthLeft - depthRight) <= 1) // 左右子树的高度差不超过1，条件之一
 47             return isBalanced(root->left) && isBalanced(root->right); // 左右子树都是AVL，条件二
 48         else
 49             return false;
 50     }
 51 
 52     int maxDepth(TreeNode *root){
 53         if (!root) return 0;
 54         return 1 + max(maxDepth(root->left), maxDepth(root->right));
 55     }
 56 
 57 };
 58 
 59 
 60 class Solution2{
 61 public:
 62     bool isBalanced(TreeNode *root){
 63         return dfsDepth(root) != -1;
 64     }
 65 
 66     int dfsDepth(TreeNode *root){
 67         if (!root) return 0;
 68         int leftDepth = dfsDepth(root->left);
 69         if (leftDepth == -1) return -1;
 70         int rightDepth = dfsDepth(root->right);
 71         if (rightDepth == -1) return -1;
 72 
 73         if (abs(leftDepth - rightDepth) > 1)
 74             return -1;
 75         return max(leftDepth, rightDepth) + 1;
 76     }
 77 };
 78 
 79 TreeNode *insert(TreeNode *root, int data){
 80     TreeNode *ptr = root;
 81     TreeNode *tempNode; // 存储的是插入节点的父节点
 82     TreeNode *newNode = new TreeNode(data);
 83 
 84     if (ptr == NULL)
 85         return newNode;
 86     else{
 87         while (ptr != NULL){
 88             tempNode = ptr;
 89             if (ptr->val >= data){
 90                 ptr = ptr->left;
 91             }else{
 92                 ptr = ptr->right;
 93             }
 94         }
 95         if (tempNode->val >= data){
 96             tempNode->left = newNode;
 97         }else{
 98             tempNode->right = newNode;
 99         }
100     }
101     return root;
102 }
103 
104 // 递归先序遍历二叉树
105 void travPre(TreeNode *root){
106     if (!root) return;
107     cout << root->val << " ";
108     travPre(root->left);
109     travPre(root->right);
110 }
111 
112 
113 int main(){
114     TreeNode *root = NULL;
115     int temp = 0;
116     cin >> temp;
117     while (temp != 0){ // 以0结尾（输入0终止）
118         root = insert(root, temp);
119         cin >> temp;
120     } // 创建一棵二叉树
121 
122     // 递归先序遍历
123     travPre(root);
124 
125     cout << endl;
126     Solution2 a;
127     cout << a.isBalanced(root);
128 }