剑指Offer-平衡二叉树

package Tree;

/**
 * 平衡二叉树
 * 输入一棵二叉树,判断该二叉树是否是平衡二叉树。
 * 平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:
 * 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
 */
public class Solution20 {
    public static void main(String[] args) {
        Solution20 solution20 = new Solution20();
        int[] array = {8, 6, 10, 5, 7, 9, 11};
        TreeNode treeNode = solution20.createBinaryTreeByArray(array, 0);
        System.out.println(solution20.IsBalanced_Solution_2(treeNode));
    }

    /**
     * 从下往上遍历,如果子树是平衡二叉树,则返回子树高度,否则返回-1
     * 时间复杂度:O(n)
     *
     * @param root
     * @return
     */
    public boolean IsBalanced_Solution_2(TreeNode root) {
        return MaxDepth_2(root) != -1;
    }

    public int MaxDepth_2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = MaxDepth_2(root.left);
        if (leftHeight == -1) {
            return -1;
        }
        int rightHeight = MaxDepth_2(root.right);
        if (rightHeight == -1) {
            return -1;
        }
        return Math.abs(leftHeight - rightHeight) > 1 ? -1 : 1 + Math.max(leftHeight, rightHeight);
    }

    /**
     * 遍历每个结点,借助一个获取树深度的递归函数,根据该结点的左右子树高度差判断是否平衡,然后递归地对左右子树进行判断。
     * 时间复杂度:O(n^2)
     *
     * @param root
     * @return
     */
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (Math.abs(MaxDepth(root.left) - MaxDepth(root.right)) > 1)
            return false;
        return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }

    public int MaxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(MaxDepth(root.left), MaxDepth(root.right));
    }

    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }

    public TreeNode createBinaryTreeByArray(int[] array, int index) {
        TreeNode tn = null;
        if (index < array.length) {
            int value = array[index];
            tn = new TreeNode(value);
            tn.left = createBinaryTreeByArray(array, 2 * index + 1);
            tn.right = createBinaryTreeByArray(array, 2 * index + 2);
            return tn;
        }
        return tn;
    }

}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏用户画像

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

输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在...

9220
来自专栏xingoo, 一个梦想做发明家的程序员

二叉排序树的删除操作

算法思想 二叉排序树,删除操作主要针对三种情况。 1 叶子节点-直接删除就可以了 2 没有左孩子的节点-直接嫁接右子树就可以了(没有右孩子的节点-直接嫁接左子树...

27580
来自专栏Android干货

Python枚举类

Enum可以把一组相关常量定义在一个class中,且class不可变,而且成员可以直接比较。

15620
来自专栏Java技术栈

二叉树实战 22 题,速度收藏吧!

深刻的理解这些题的解法思路,在面试中的二叉树题目就应该没有什么问题,甚至可以怒他,哈哈。

10630
来自专栏desperate633

LintCode 二叉树的层次遍历 II题目代码

给出一棵二叉树,返回其节点值从底向上的层次序遍历(按从叶节点所在层到根节点所在的层遍历,然后逐层从左往右遍历)

10140
来自专栏猿人谷

判断二叉树是不是平衡

平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超...

21660
来自专栏章鱼的慢慢技术路

笔试常考题型之二叉树的遍历

19240
来自专栏java学习

让你更好的理解什么是二叉树?

二叉树 6.2.1 二叉树的概念 二叉树(Binary Tree)是结点的有限集合,这个集合或者为空,或者是由一个根结点和两颗互不相交的分别称为左子树和右子树的...

830110
来自专栏武培轩的专栏

剑指Offer-按之字形顺序打印二叉树

package Tree; import java.util.ArrayList; import java.util.LinkedList; import j...

29040
来自专栏章鱼的慢慢技术路

笔试常考题型之二叉树的遍历

18850

扫码关注云+社区

领取腾讯云代金券