1 /*************************************************************************  2     > File Name: 37_TreeDepth.cpp  3     > Author: Juntaran  4     > Mail: JuntaranMail@gmail.com  5     > Created Time: 2016年09月03日 星期六 09时49分38秒  6  ************************************************************************/  7   8 #include <stdio.h>  9 #include <malloc.h> 10 #include <math.h> 11  12 // 二叉树结构体 13 struct BinaryTree 14 { 15     int val; 16     struct BinaryTree* left; 17     struct BinaryTree* right; 18 }; 19  20 BinaryTree* createTree() 21 { 22     BinaryTree* root = (BinaryTree*)malloc(sizeof(BinaryTree)); 23     root->val = 1; 24     root->left = (BinaryTree*)malloc(sizeof(BinaryTree)); 25     root->left->val = 2; 26     root->right = (BinaryTree*)malloc(sizeof(BinaryTree)); 27     root->right->val = 3; 28     root->left->left = (BinaryTree*)malloc(sizeof(BinaryTree)); 29     root->left->left->val = 4; 30     root->left->left->left = NULL; 31     root->left->left->right = NULL; 32     root->left->right = (BinaryTree*)malloc(sizeof(BinaryTree)); 33     root->left->right->val = 5; 34     root->left->right->right = NULL; 35     root->left->right->left = (BinaryTree*)malloc(sizeof(BinaryTree)); 36     root->left->right->left->val = 7; 37     root->left->right->left->left = NULL; 38     root->left->right->left->right = NULL; 39     root->right->right = (BinaryTree*)malloc(sizeof(BinaryTree)); 40     root->right->right->val = 6; 41     root->right->left = NULL; 42     root->right->right->left = NULL; 43     root->right->right->right = NULL; 44     // root->right->right->right = (BinaryTree*)malloc(sizeof(BinaryTree)); 45     // root->right->right->right->val = 8; 46     // root->right->right->right->left = root->right->right->right->right = NULL; 47      48     return root; 49 } 50  51 // 二叉树中序遍历 52 void InOrder(BinaryTree* root) 53 { 54     if (root == NULL) 55         return; 56      57     InOrder(root->left); 58     printf("%d ", root->val); 59     InOrder(root->right); 60 } 61  62 // 二叉树的深度 63 int TreeDepth(BinaryTree* root) 64 { 65     if (root == NULL) 66         return 0; 67      68     int left  = TreeDepth(root->left); 69     int right = TreeDepth(root->right); 70      71     return (left>right) ? (left+1) : (right+1); 72 } 73  74 // 判断一棵树是不是平衡二叉树 75 bool isBalanced(BinaryTree* root) 76 { 77     if (root == NULL) 78         return true; 79      80     int left  = TreeDepth(root->left); 81     int right = TreeDepth(root->right); 82      83     int diff = abs(left - right); 84     if (diff > 1) 85         return false; 86      87     return isBalanced(root->left) && isBalanced(root->right); 88 } 89  90 // 后序遍历方法 91 bool isBalanced2(BinaryTree* root, int* depth) 92 { 93     if (root == NULL) 94     { 95         *depth = 0; 96         return true; 97     } 98     int left, right; 99     if (isBalanced2(root->left, &left) && isBalanced2(root->right, &right))100     {101         int diff = abs(left - right);102         if (diff <= 1)103         {104             *depth = 1 + (left>right ? left : right);105             return true;106         }107     }108     return false;109 }110 111 bool isBalanced2(BinaryTree* root)112 {113     int depth = 0;114     return isBalanced2(root, &depth);115 }116 117 118 119 int main()120 {121     BinaryTree* test = createTree();122     InOrder(test);123     int depth = TreeDepth(test);124     printf("\ndepth is %d\n", depth);125     if (isBalanced2(test) == true)126         printf("Balance\n");127     else128         printf("No Balance\n");129     130 }