leetcode 110. 平衡二叉树

难度:简单
频次:61

题目:

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

本题中,一棵高度平衡二叉树定义为:

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

leetcode 110. 平衡二叉树
leetcode 110. 平衡二叉树
leetcode 110. 平衡二叉树

解题思路:算深度+递归

注意

  • 这里算深度的递归函数,其实跟104 二叉树的最大深度的拆分树的递归版本一行,基本一字不差。
  • 在主函数里就两个东西
    - 判断是否为空,为空返回true
    - 判断是否符合三个条件
    - 当前子树是否符合高度差为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 {
    public boolean isBalanced(TreeNode root) {
        if(root==null) return true;
        //判断是否平衡,任意一颗左子树跟右子树之间的高度差不超过1
        //也就是判断3个条件:当前子树是否符合,左子树是否符合,右子树是否符合
        return Math.abs(depth(root.left)-depth(root.right))<2&&isBalanced(root.left)&&isBalanced(root.right);
    }
    public int depth(TreeNode root){
        if(root==null) return 0;
        int left=depth(root.left);
        int right=depth(root.right);
        return Math.max(left,right)+1;
    }
}
上一篇:如何低成本的搭建一个真实的Kubernetes集群


下一篇:Request processing failed; nested exception is org.springframework.dao.DataIntegrityViolationExcepti