判断平衡二叉树(递归)

平衡二叉树

http://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222

描述

题目描述

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

在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

注：我们约定空树是平衡二叉树。

示例

输入：{1,2,3,4,5,6,7}
返回值：true

引言

有关树的题目很多都可以使用递归解决，但需要注意栈溢出的问题。

递归只要关心递归方法能实现的功能，而无需陷入其中去理解每一层递归的细节，否则只会自行提高题目难度

知识点：二叉树，递归
难度：二星

题解

解题思路

一看到树的题目就要想到使用递归解决问题，而且有时候可以通过使用递归、遍历等框架解题。

本题可以使用自顶向下的暴力法来遍历整棵树，时间复杂度相对较高

也可以使用自底向上的递归，最关键就是要阻断递归，递归到一定情况要结束当前节点递归，降低时间复杂度

方法一：暴力法：自顶向下

算法流程：

通过比较每个节点的左右子树的最大高度差, 来判断此子树是否是二叉平衡树。
若树的所有子树都平衡时，该树才是平衡二叉树。

Java 版本代码如下：

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root == null) return true;
        // 高度差不能大于1，并且左右子树也是同样高度差要小于等于1
        return Math.abs(depth(root.left) - depth(root.right)) <= 1 && IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }

    private int depth(TreeNode root) {
        if (root == null) {
            return 0;  
        } 
         // 左右子树中高度较大的作为当前节点高度
        return Math.max(depth(root.left), depth(root.right)) + 1;
    }
}

Python 版本代码如下：

class Solution:
    def IsBalanced_Solution(self, root: TreeNode) -> bool:
        if not root: return True
        # 高度差不能大于1，并且左右子树也是同样高度差要小于等于1
        return abs(self.depth(root.left) - self.depth(root.right)) <= 1 and \
            self.IsBalanced_Solution(root.left) and self.IsBalanced_Solution(root.right)

    def depth(self, root):
        if not root: return 0
        # 左右子树中高度较大的作为当前节点高度
        return max(self.depth(root.left), self.depth(root.right)) + 1

复杂度分析：

时间复杂度 O(Nlog2N)：最差情况下，需要遍历树所有节点判断是否平衡，需要O(N)。判断每个节点最大高度需要递归左右子树，需要占用 O(log2N)，所以总共占用O(Nlog2N)
空间复杂度O(N)：最差情况下（树退化为链表时），递归需要使用O(N) 的栈空间。

方法二：自底向上递归

图解

算法流程：

判断空树，题目要求空树也是平衡二叉树
递归计算当前root左右子树的高度差
注意：递归过程中有左/右子树不平衡,则该树不平衡，相当于可行性剪枝，没必要遍历所有节点
递归到底后，自底向顶，每次+1，不断计算高度，直到递归到某个节点使得左右子树高度差大于1，则返回-1表示不平衡
左右子树中高度较高的, 作为当前节点的高度, 用于向上递归判断是否平衡
递归终止条件：
- root 为 null
- 左右子树高度差大于1，即左右子树其中一个节点返回-1，则递归终止，阻断递归，表示不是平衡二叉树
递归方法的功能：获取当前节点的树的高度

Java 版本代码如下：

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        // 空树也是平衡二叉树
        if(root == null) {
            return true;
        }
        return getHeight(root) != -1;
    }

    public int getHeight(TreeNode root) {
        if(root == null) {
            return 0;
        }
        // 递归计算当前root左右子树的高度差
        int left = getHeight(root.left);
        // 当前节点左子树不平衡,则该树不平衡，相当于可行性剪枝，没必要遍历所有节点
        if(left < 0) {
            return -1;
        } 
        int right = getHeight(root.right);
        if(right < 0) {
            return -1;
        } 
        // 自底向顶，每次+1，不断计算高度，直到递归到某个节点使得左右子树高度差大于1，则返回-1表示不平衡
        // 左右子树中高度较高的, 作为当前节点的高度, 用于向上递归判断是否平衡
        return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
    }
}

Python 版本代码如下：

class Solution:
    # 计算root节点的高度
    def high(self,root):
        if root == None:
            return 0
        left = self.high(root.left)
        right = self.high(root.right)
        ans = max(left,right)+1
        return ans

    def IsBalanced_Solution(self, pRoot):
        if pRoot == None:
            return True
        # 提前阻断，可行性剪枝
        if not self.IsBalanced_Solution(pRoot.left):
            return False
        if not self.IsBalanced_Solution(pRoot.right):
            return False
        highleft = self.high(pRoot.left)
        highright = self.high(pRoot.right)
        isbalance = highleft - highright
        # 当前节点高度差
        if isbalance > 1 or isbalance < -1:
            return False
        return True
        # write code here