110.平衡二叉树 | 分治思想

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

平衡二叉树

https://leetcode.cn/problems/balanced-binary-tree/submissions/

分治基本思路

一棵树是否是平衡二叉树, 是取决与它每个节点对应的子树是否是平衡二叉树, 只要有一个节点对应的子树不是, 这棵树就不是平衡二叉树

平衡二叉树 : 每个节点的左右两个子树的高度差的绝对值不超过 1

基本思路其实很简单 :

平衡二叉树需要判断每个节点的子树是否是平衡二叉树(大问题拆成小问题), 所以, 我们需要遍历二叉树
当前节点的高度, 其实就是当前节点到叶子节点的最大深度
所以我们获取高度以后, 在后序位置进行判断

分治代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    boolean isBalance = true;

    public boolean isBalanced(TreeNode root) {
        return getHeight(root) == -1 ? false : true;
    }
    
    // 如果是平衡二叉树就返回高度, 不是就返回 -1
    public int getHeight(TreeNode root) {

        if(root == null) {
            return 0;
        }

        int leftHeight = getHeight(root.left);
        // 一棵树是否是平衡二叉树, 是取决与它每个节点对应的子树是否是平衡二叉树, 
        // 只要有一个节点对应的子树不是, 这棵树就不是平衡二叉树
        
        if(leftHeight == -1) {
            return -1;
        }
        
        int rightHeight = getHeight(root.right);
        
        if(rightHeight == -1) {
            return -1;
        }

        if(Math.abs(leftHeight - rightHeight) > 1) {
            // 不是
            return -1;
        }

        return 1 + Math.max(leftHeight , rightHeight);
    }
   
}