LintCode 平衡二叉树题目分析代码

题目

给定一个二叉树,确定它是高度平衡的。对于这个问题,一棵高度平衡的二叉树的定义是:一棵二叉树中每个节点的两个子树的深度相差不会超过1。

样例 给出二叉树 A={3,9,20,#,#,15,7} , B={3,#,20,15,7}

balence.PNG

二叉树A是高度平衡的二叉树,但是B不是

分析

首先求深度,然后判断深度相差是否超过1,注意递归的使用

代码

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: True if this Binary tree is Balanced, or false.
     */
    public boolean isBalanced(TreeNode root) {
        // write your code here
        if(root == null)
            return true;
        int left = depth(root.left);
        int right = depth(root.right);
        if(Math.abs(left-right) <= 1)
        {
            return isBalanced(root.left) && isBalanced(root.right);
        }
        else
            return false;
    }
    
    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;
    }
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序生活

二叉树的深度

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

27240
来自专栏xcywt

《大话数据结构》树以及赫夫曼编码的例子

第六章 树 6.2 树的定义 树(Tree)的n个结点的有限集。当n=0时,称为空树。 任意一个非空树中: 1)有且仅有一个特定的称为根(root)的结点 2)...

45760
来自专栏Python专栏

【数据结构与算法】一起搞定面试中的二叉树题目(二)

22730
来自专栏C/C++基础

求二叉树的深度和宽度

题目: 输入一个二叉树的根节点,求该树的深度。从根节点到叶子节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度包含的节点数为为树的深度,即二...

23720
来自专栏weixuqin 的专栏

数据结构学习笔记(树、二叉树)

27030
来自专栏从流域到海域

校招必考:根据二叉树遍历序列确定二叉树

根据二叉树的前序遍历和中序遍历求其后序遍历或者根据二叉树的后序遍历和中序遍历求其前序遍历是腾讯等校招的必考题,下面我们就来分析一下解题思路。 这道题本质上...

23950
来自专栏琯琯博客

PHP二叉树(三):红黑树

31640
来自专栏desperate633

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

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

9940
来自专栏尾尾部落

[剑指offer] 二叉树的深度

输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。

8920
来自专栏武培轩的专栏

剑指Offer-把二叉树打印成多行

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

39340

扫码关注云+社区

领取腾讯云代金券