剑指offer之【平衡二叉树】

题目：

　　平衡二叉树

链接：

　　https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222?tpId=13&tqId=11192&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述：

　　输入一棵二叉树，判断该二叉树是否是平衡二叉树。

思路：

　　根据计算二叉树深度的方法进行改进，只需深度遍历一次，从叶节点向跟节点方向行进。

代码：

 1 class Solution {
 2 public:
 3     bool IsBalanced_Solution(TreeNode* pRoot)
 4     {
 5         int deep;
 6         return DFS(pRoot,deep);
 7 
 8 
 9     }
10     bool DFS(TreeNode* root,int & deep){
11         if(root == nullptr){
12               deep = 0;
13             return true;
14         }
15         int ld,rd;
16         if(DFS(root->left,ld)&& DFS(root->right,rd)){
17             if(abs(rd-ld)<=1){
18                 deep = max(ld,rd)+1;
19                 return true;
20             }
21         }
22         return false;
23     }
24 };