【Offer】[55-2] 【平衡二叉树】

题目描述
思路分析
测试用例
Java代码
代码链接

题目描述

　　输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左、右子树的深度相差不超过1,那么它就是一棵平衡二叉树。例如，图中的二叉树就是一棵平衡二叉树。

牛客网刷题地址

思路分析

　　在求二叉树的深度的过程中判断左右子树之间的高度差，如果高度差大于1 ，就返回-1，说明不是平衡二叉树，否则返回二叉树的深度。

测试用例

功能测试：平衡的二叉树;不是平衡的二叉树;二叉树中所有节点都没有左/右子树。
特殊输入测试：二叉树中只有一个节点;二叉树的头节点为nullptr指针。

Java代码

public class Offer055_02 {

    public static void main(String[] args) {

        test1();

        test2();

        test3();

    }

    public static  boolean IsBalanced_Solution(TreeNode root) {

        return Solution1(root);

    }

    private static boolean Solution1(TreeNode root) {

        return getDepth(root)!=-1;

    }

    private static int  getDepth(TreeNode root) {

        if(root==null) return 0;

        int leftDep = getDepth(root.left);

        if(leftDep == -1) return -1;

        int rightDep = getDepth(root.right);

        if(rightDep==-1) return -1;

        return Math.abs(leftDep-rightDep) >1 ? -1 :(Math.max(leftDep,rightDep) + 1);

    }

    private static void test1() {

    }

    private static void test2() {

    }

    private static void test3() {

    }

}

代码链接

剑指Offer代码-Java

巴特西

【Offer】[55-2] 【平衡二叉树】

题目描述

思路分析

测试用例

Java代码

代码链接

最新文章

热门文章