当前位置：网站首页>"110 Balanced Binary Tree Judgment" in leetCode's 14-day binary tree series

"110 Balanced Binary Tree Judgment" in leetCode's 14-day binary tree series

2022-08-11 03:51:00 【small double】

leetCode 110 平衡二叉树判断

题目描述

给定一个二叉树,判断它是否是高度平衡的二叉树.
本题中,一棵高度平衡二叉树定义为：
一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1.

示例

给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4

题目解析

You can read about basics such as balanced binary trees《Implementation of binary tree and balanced binary tree data structure》,根据题目的意思,We need to determine the height of its left and right subtrees for each node,And ensure that its height difference does not exceed1,That is, the balance factor of each node does not exceed1,如果查过1It is not a balanced binary tree,At this point, the balancing operation is performed,However, this is not the content of this topic.

In fact, just use the recursive method,And count the height of the left and right subtrees to compare,代码如下：

class Solution {
    
    public boolean isBalanced(TreeNode root) {
    
        if (root == null) {
    
            return true;
        }

        if (!isBalanced(root.left) || !isBalanced(root.right)) {
    	//Returns if there are left and right subtrees that do not satisfy the balanced binary tree conditionfalse
            return false;	
        }

        int leftDepth = maxDepth(root.left) + 1;
        int rightDepth = maxDepth(root.right) + 1;
        if (Math.abs(leftDepth - rightDepth) > 1) {
    
            return false;
        }
        return true;
    }

    public int maxDepth(TreeNode root) {
    	//Calculate the maximum depth of each tree
        if (root == null) {
    
            return 0;
        }
        if (root.left == null && root.right == null) {
    
            return 1;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}