平衡二叉树
参与人数：1135时间限制：1秒空间限制：32768K通过比例：32.36%最佳记录：0 ms|0K
题目描述
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
题目链接：?rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
首先我们知道左右子树深度差不超过1，，那么就是一棵平衡树。
由上一题求深度拓展 >>如何求深度<<如果我们直接在上题上加一个判断条件，那么递归了很多重复的数。如何只递归一次呢，那么就来记录下每次递归的深度吧。
依照这样的思想，我把每次递归的左右深度通过&引用递归，那么就可以解决了。
<对了，这里空树是算平衡的还是。。。>
#include<stdio.h>#include<algorithm>using namespace std;struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}};class Solution {public:bool IsBalanced_Solution(TreeNode* pRoot) {// if(!pRoot) return false;//空树是平衡树吗？int deep=0;return IsBalanced_Solution(pRoot,deep);}bool IsBalanced_Solution(TreeNode* pRoot,int &deep){if(!pRoot){deep=0;return true;}int left;int right;if(IsBalanced_Solution(pRoot->left,left) && IsBalanced_Solution(pRoot->right,right)){if(left-right<=1 && left-right>=-1){deep=1+max(left,right);return true;}}return false;}};int main(){return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
才能做到人在旅途，感悟人生，享受人生。
