剑指offer--55.II 平衡二叉树（思路搞明白）

深藏阁楼爱情的钟 2023-02-15 12:59 3阅读 0赞

## 题目描述 ##

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

限制：

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

## 思路：递归（树的深度、深度差） ##

分为两部分：求树的深度、左右子树的深度差

## 解决方法 ##

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        //树的深度
        public int depth(TreeNode root){
        
            //递归出口
            if(root == null)
                return 0;
            
            int left = depth(root.left);
            int right = depth(root.right);
    
            return (left > right) ? left+1 : right+1;
        }
        //深度差
        public boolean isBalanced(TreeNode root) {
        
            //递归出口
            if(root == null)
                return true;
            //头节点的左右子树深度left right
            int left = depth(root.left);
            int right = depth(root.right);
            return Math.abs(left-right) <= 1 && isBalanced(root.left) && isBalanced(root.right);   //所有的左右子树都得满足平衡二叉树
    
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，3人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指offer--55.II 平衡二叉树（思路搞明白）

题目描述输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。示例 1: 给定二叉树 \

深藏阁楼爱情的钟/ 2023年02月15日 12:59/ 0 赞/ 4 阅读

相关剑指offer | 55 - II. 平衡二叉树

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

我就是我/ 2022年12月28日 00:55/ 0 赞/ 109 阅读

相关剑指 Offer 55 - II. 平衡二叉树

题目输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。示例 1: 给定二叉树 \[

喜欢ヅ旅行/ 2022年12月19日 08:39/ 0 赞/ 94 阅读

相关【剑指Offer】55.2 平衡二叉树

[NowCoder][] 题目描述平衡二叉树左右子树高度差不超过 1。 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpd

叁歲伎倆/ 2022年12月02日 04:27/ 0 赞/ 101 阅读

相关剑指 Offer 55 - II. 平衡二叉树 || 110. 平衡二叉树

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

以你之姓@/ 2022年11月05日 03:19/ 0 赞/ 177 阅读

相关剑指offer 平衡二叉树

1.题目描述输入一棵二叉树，判断该二叉树是否是平衡二叉树。 2.分析平衡二叉树在leetcode刷题时也做过，附上[题目链接][Link 1] 之前写的解题

灰太狼/ 2022年06月15日 05:21/ 0 赞/ 188 阅读

相关【剑指offer】面试题55（2）：平衡二叉树

题目输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中的任意节点的左、右子树的深度相差不超过1，那么它就是一棵平衡二叉树。思路我们用后序

超、凢脫俗/ 2022年06月11日 07:08/ 0 赞/ 152 阅读

相关剑指offer 平衡二叉树

题目描述输入一棵二叉树，判断该二叉树是否是平衡二叉树。解题思路平衡二叉树是这样定义的：平衡二叉树（Balanced Binary Tree）又被称为A

电玩女神/ 2022年05月21日 05:18/ 0 赞/ 188 阅读

相关剑指offer:平衡二叉树

题目描述输入一棵二叉树，判断该二叉树是否是平衡二叉树。 AC C++ Solution: 递归判断左右子树的高度差并记录高度返回给父节点 class So

迈不过友情╰/ 2022年04月10日 09:15/ 0 赞/ 210 阅读

相关剑指Offer-平衡二叉树

题目描述输入一棵二叉树，判断该二叉树是否是平衡二叉树。平衡二叉树的定义为：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

刺骨的言语ヽ痛彻心扉/ 2022年02月19日 11:43/ 0 赞/ 207 阅读