剑指offer 39. 是否为平衡二叉树

39. 是否为平衡二叉树

题目描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树任意结点的左右子树高度差不大于1就是平衡二叉树。

C++解法

 1 class Solution {
 2 public:
 3     bool flag = true;    // 记录是否为平衡二叉树，不是则为false
 4     bool IsBalanced_Solution(TreeNode* pRoot) {
 5         preOrder(pRoot);
 6         return flag;
 7     }
 8     // 前序递归遍历
 9     int preOrder(TreeNode* pRoot){
10         if(pRoot && flag == true){
11             int leftH = preOrder(pRoot->left);
12             int rightH = preOrder(pRoot->right);
13             if(abs(leftH - rightH) > 1)
14                 flag = false;
15             return ((leftH >= rightH) ? (leftH + 1) : (rightH + 1));
16         }
17         return 0;
18     }
19     
20 };

leetcode运行时间为1ms, 空间为38.8mb

复杂度分析：

时间复杂度：一定会遍历树的所有结点，即使很早就发现了该树是不平衡树，所以时间复杂度为O(n)

空间复杂度：递归深度为树的最大高度，高度平均为O(logn), 最坏为O(n),所以空间复杂度也是平均为O(logn), 最坏为O(n)

Java解法

结题思路大致和上面一样，只不过这里没有借助一个标记flag, 直接通过返回树高-1来表示树不平衡。而且统计树高的函数进行了剪枝，只要左子树不平衡或者右子树不平衡直接返回整棵树不平衡，减少后续无效计算。

 1 class Solution {
 2     
 3     public boolean isBalanced(TreeNode root) {
 4         return treeHeight(root) != -1;
 5     }
 6 
 7     // 统计树高的辅助函数
 8     public int treeHeight(TreeNode root){
 9         // 统计左右子树高度，只有两个高度同时不为-1, 才继续执行，否则直接返回，可以省去很多无效计算
10         if(root == null){
11             return 0;
12         }else{
13             int leftHeight = treeHeight(root.left);
14             if(leftHeight == -1){       // 如果左子树为不平衡树，直接返回整棵树为不平衡树
15                 return -1;
16             }
17             int rightHeight = treeHeight(root.right);
18             if(rightHeight == -1){      // 如果右子树为不平衡树，直接返回整棵树为不平衡树
19                 return -1;
20             }
21             return Math.abs(leftHeight - rightHeight) > 1 ? -1 : Math.max(leftHeight, rightHeight) + 1;
22         }
23     }
24 }

leetcode运行时间为1ms, 空间为39.1MB

复杂度分析：

时间复杂度：最坏情况下会遍历整棵树的所有结点，复杂度为O(n), 但是算法经过了剪枝处理，复杂度应该会比思路一好一些。

空间复杂度：树的高度就是栈的深度，高度平均为O(logn), 最坏为O(n),所以空间复杂度也是平均为O(logn), 最坏为O(n)

Java解法二：

思路参考：https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/solution/mian-shi-ti-55-ii-ping-heng-er-cha-shu-cong-di-zhi/

递归判断左右子树是否平衡，统计左右子树高度差。这个方法会有很多重复计算

 1 class Solution {
 2 
 3     public boolean isBalanced(TreeNode root) {
 4         if(root == null){
 5             return true;
 6         }
 7         // 递归判断左右子树是否平衡，统计左右子树高度差
 8         return isBalanced(root.left) && isBalanced(root.right) && Math.abs(treeHeight(root.left) - treeHeight(root.right)) < 2;
 9     }
10 
11     // 统计树高的辅助函数
12     public int treeHeight(TreeNode root){
13         if(root == null){
14             return 0;
15         }
16         return Math.max(treeHeight(root.left), treeHeight(root.right)) + 1;
17     }
18 }

leetcode运行时间为1ms, 空间为39.4MB