平衡二叉树(剑指offer55-II 力扣110)Java

人生之路不会是一帆风顺的,我们会遇上顺境,也会遇上逆境,在所有成功路上折磨你的,背后都隐藏着激励你奋发向上的动机,人生没有如果,只有后果与结果,成熟,就是用微笑来面对一切小事。

导读:本篇文章讲解 平衡二叉树(剑指offer55-II 力扣110)Java,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

一、题目描述

输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过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 。

限制:

0 <= 树的结点个数 <= 10000

二、Java代码实现

        1、自顶向下的递归

        保证自己满足左右子树深度差小于1的同时,自己的左子树和右子树也满足这个条件。

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

    public boolean isBalanced(TreeNode root) {

        if(root==null){
            return true;
        }
        return (Math.abs(dfs(root.left)-dfs(root.right))<=1 && isBalanced(root.left) && isBalanced(root.right));
    }

    int dfs(TreeNode node){
        if(node == null){
            return 0;
        }

        int left = dfs(node.left);
        int right = dfs(node.right);

        return Math.max(left, right)+1;
    }
}

        2、自底向上的递归 

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

    public boolean isBalanced(TreeNode root) {

        return dfs(root)>=0;
    }

    int dfs(TreeNode node){
        if(node == null){   //叶子节点为深度为0
            return 0;
        }

        int left = dfs(node.left);
        int right = dfs(node.right);

        if(left==-1 || right==-1 || Math.abs(left-right)>1){    
            //有深度差不满足的,就直接将-1传递上去
            return -1;
        } else {
            //深度差满足,就将深度传上去
            return Math.max(left, right)+1;
        }
    }
}

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/125007.html

(0)
飞熊的头像飞熊bm

相关推荐

发表回复

登录后才能评论
极客之音——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!