39平衡二叉树

题目描述

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

思路：
利用上一题树的深度。
再遍历树的每个节点时，调用depth得到左右子树的深度，如果每个节点的左右子树的深度差都不超过
1，则此树是一个平衡二叉树。

 1 public class Solution {
 2     public boolean IsBalanced_Solution(TreeNode root) {
 3         if(root==null) return true;
 4         int left = depth(root.left);
 5         int right = depth(root.right);
 6         if(Math.abs(left-right)>1) return false;
 7         return IsBalanced_Solution(root.left) &&IsBalanced_Solution(root.right);
 8     }
 9     private int depth(TreeNode root){
10         if(root==null) return 0;
11         int left = depth(root.left);
12         int right = depth(root.right);
13         return left>right?left+1:right+1;
14     }
15 }

c++:20180728

 1 class Solution {
 2 public:
 3     bool IsBalanced_Solution(TreeNode* root) {
 4         if(root==NULL) return true;
 5         int left = depth(root->left);
 6         int right = depth(root->right);
 7         if(abs(left-right)>1) return false;
 8         return IsBalanced_Solution(root->left)&&IsBalanced_Solution(root->right);
 9         
10     }
11     int depth(TreeNode* root){
12         if(root==NULL) return 0;
13         return max(depth(root->left),depth(root->right)) +1;
14     }
15 };