判断一个树是否为平衡二叉树

vlambda
2020-06-12

判断一个树是否为平衡二叉树

题目：判断一棵树是否为平衡二叉树

描述：给定一棵树，要求判断其是否为平衡二叉树，左右高度差的绝对值不大于1

题解：先求得左右各自的深度，在做比较，，如果树的高度为0就返回true，如果高度差大于1就返回false，如果小于1，就对左右分别进行此操作；

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */
//想法先求左右两个的高度，然后比较绝对值是否大于1//求高度int deepth(struct TreeNode* t){ int h1,h2; if(t==NULL)  { return 0; } else { h1=deepth(t->left); h2=deepth(t->right); if(h1>h2) { return (h1+1); } else { return (h2+1); } }}bool isBalanced(struct TreeNode* root){ if(root==NULL) return true;//如果为空则true int deepthleft=deepth(root->left); int deepthright=deepth(root->right); //求得左右深度 if((deepthleft-deepthright)>1||(deepthleft-deepthright)<-1) return false; return isBalanced(root->left)&&isBalanced(root->right);}