LeetCode110.平衡二叉树

题目链接:LeetCode110

 平衡二叉树的定义是一个二叉树每个结点的左右两个子树的高度差绝对值不超过1(可以是1),用一个结构体来保存某个结点的信息(包括是否是平衡树,高度多少),算法流程如下:

  1. 判断当前结点的左子树是否为平衡二叉树
  2. 判断当前结点的右子树是否为平衡二叉树
  3. 判断左子树与右子树的高度差的绝对值是否大于1

 假设左子树已经不是平衡二叉树了,2,3都不用判断了,3判断的前提是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 ReturnData process(TreeNode head) {
        if(head == null)
            return new ReturnData(true,0);
        
        ReturnData leftData = process(head.left);
        if(!leftData.isB)
            return new ReturnData(false,0);
        
        ReturnData rightData = process(head.right);
        if(!rightData.isB)
            return new ReturnData(false,0);
        
        if(Math.abs(leftData.h - rightData.h) > 1)
            return new ReturnData(false,0);
        return new ReturnData(true,Math.max(leftData.h,rightData.h) + 1);//因为还要算上当前结点,所以要+1
    }
    public boolean isBalanced(TreeNode root) {
        return process(root).isB;
    }
}
class ReturnData {
    boolean isB;
    int h;
    ReturnData(boolean isB,int h) {
        this.isB = isB;
        this.h = h;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏书山有路勤为径

二叉查找树转换为较大树

Leetcode 538 已知一个二叉查找树,将它转换为一个较大树,即所有的二叉查找树的节点,赋值为该节点本身的值与该节点大的节点的值的和

842
来自专栏熊二哥

深入入门系列--Data Structure--04树

终于有机会重新回头学习一下一直困扰自身多年的数据结构了,赶脚棒棒哒。一直以来,对数据结构的掌握基本局限于线性表,稍微对树有一丢丢了解,而对于图那基本上就是不懂(...

1859
来自专栏青玉伏案

算法与数据结构(十一) 平衡二叉树(AVL树)(Swift版)

今天的博客是在上一篇博客的基础上进行的延伸。上一篇博客我们主要聊了二叉排序树,详情请戳《二叉排序树的查找、插入与删除》。本篇博客我们就在二叉排序树的基础上来聊聊...

2397
来自专栏WindCoder

DateUtil-常用关于date的工具类备份

811
来自专栏kevindroid

leetcode110 Balanced Binary Tree

1465
来自专栏开发与安全

算法:二叉排序树的删除节点策略及其图形化(二叉树查找)

二叉排序树(BST,Binary Sort Tree)具有这样的性质:对于二叉树中的任意节点,如果它有左子树或右子树,则该节点的数据成员大于左子树所有节点的数据...

2169
来自专栏趣学算法

数据结构 第11讲 二叉树及其创建

二叉树(Binary Tree)是n(n≥0)个结点所构成的集合,它或为空树(n = 0);或为非空树,对于非空树T:

1132
来自专栏程序生活

二叉树的深度

题目描述 输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。 代码实现 递归实现 # ...

2544
来自专栏日常分享

Java 通过先序中序序列生成二叉树

  二叉树的前序以及后续序列,以空格间隔每个元素,重构二叉树,最后输出二叉树的三种遍历方式的序列以验证。

1501
来自专栏武培轩的专栏

剑指Offer-二叉树中和为某一值的路径

题目描述 输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。 思路 回...

3074

扫码关注云+社区