110、平衡二叉树

leetcode

Created At : 2020-07-26 00:19

Count:417 Views 👀 :

Comment:

110、平衡二叉树
1. 示例 1:
2. 示例 2:
题解
1. 1、自顶向下递归
2. 2、自下而上递归

110、平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

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

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7
返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4
返回 false 。

链接：https://leetcode-cn.com/problems/balanced-binary-tree

题解

1、自顶向下递归

先检查上层是否符合平衡。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int height(TreeNode root) {
        if (root == null) {
            retrurn -1;
        }
        // 尾递归
        return 1 + Math.max(height(root.left),height(root.right));
    }

    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 先求深度，在递归
        return Math.abs(height(root.left) - height(root.right)) < 1 && isBalanced(root.left) && isBalanced(root.right);
    }
}

2、自下而上递归

先检查下层是否平衡

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

final class TreeInfo {
    public final int height;
    public final boolean balanced;

    public TreeInfo(int height,boolean balanced) {
        this.height = height;
        this.balanced = balanced;
    }
}
class Solution {
    private TreeInfo isBalancedTreeHelper(TreeNode root) {
        if (root == null) {
            return new TreeInfo(-1,true);
        }

        TreeInfo left = isBalancedTreeHelper(root.left);
        if (!left.balanced) {
            return new TreeInfo(-1,false);
        }
        TreeInfo right = isBalancedTreeHelper(root.right);
        if (!right.balanced) {
            return new TreeInfo(-1,false);
        }

        if (Math.abs(left.height - right.height) < 2) {
            return new TreeInfo(Math.max(left.height, right.height) + 1,true);
        }

        return new TreeInfo(-1, false);
   }

    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 先求深度，在递归
        return isBalancedTreeHelper(root).balanced;
    }
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com