二叉树 平衡二叉树110

需求

给定一个二叉树，判断它是否是
平衡二叉树

示例 1：

二叉树
输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

二叉树
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

leetcode题目链接

概念：

平衡二叉树： 二叉树任何一个节点的左右子树的高度差小于等于一。

思路

递归法：
根据平衡二叉树的概念，对树进行遍历，如果左右子节点高度>1 说明不是平成二叉树。
层遍历法：
上面我们实现了二叉树最小高度。那么我们在找出最大高度，只要差值>1说明不是平衡二叉树。

/**
 * 110. 平衡二叉树
 */
public class IsBalanced110 {
    public boolean isBalanced(TreeNode root) {
        int high = balaced(root);
        return high == -1 ? false : true;
    }

    /**
     * 求高度均使用递归后续遍历
     * 求深度均使用递归前序遍历
     */
    public int balaced(TreeNode node) {
        int result = 0;
        // 任一节点左右子树高度差<=1
        if (node == null) return 0;
        int leftHigh = balaced(node.left);// 左
        int rightHigh = balaced(node.right);// 右
        // 子树返回已不是平衡平衡二叉树直接返回
        if (leftHigh == -1 || rightHigh == -1) return -1;
        if (Math.abs(leftHigh - rightHigh) > 1) return -1;

        result = 1 + Math.max(leftHigh, rightHigh);// 中
        return result;
    }

    /**
     * 层序遍历，广度遍历
     */
    public boolean isBalancedGd(TreeNode root) {
        if (root == null) return true;
        int minHigh = 0;
        int maxHigh = 0;
        boolean isminHigh = true;

        Deque<TreeNode> deque = new LinkedList();
        deque.offer(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            if (isminHigh) minHigh++;
            maxHigh++;
            while (size-- > 0) {
                TreeNode node = deque.pop();
                if (node.left != null) deque.offer(node.left);
                if (node.right != null) deque.offer(node.right);
                // 找到最小高度，停止最小高度赋值
                if (node.left == null && node.right == null) isminHigh = false;
            }
        }
        return Math.abs(minHigh - maxHigh) <= 1;
    }
}

验证结果
验证结果