HomeArchivesCategoriesLabelMomentsPhotosLinkAbout

LeetCode 110. 平衡二叉树

学习
64
0
0
2022-06-04
LeetCode 110. 平衡二叉树

LeetCode 110. 平衡二叉树

问题描述

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

示例 1：

示例1

输入：root = [3,9,20,null,null,15,7] 输出：true

示例 2：

示例2

输入：root = [1,2,2,3,3,null,null,4,4] 输出：false

示例 3：

输入：root = [] 输出：true

提示：

  • 树中的节点数在范围 [0, 5000] 内

  • -10^4 <= Node.val <= 10^4

思路

方法一：二叉平衡树判定

该二叉树的根节点为 root，那么该二叉树为平衡二叉树的充要条件是：

  1. 根节点的左右两个子树的高度差的绝对值不超过 1；

  2. 根节点的左子树为平衡二叉树；

  3. 根节点的右子树也为平衡二叉树。

代码实现（Java）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        } else {
        	/*
        		该二叉树的根节点为 root，那么该二叉树为平衡二叉树的充要条件是：
				(1) 根节点的左右两个子树的高度差的绝对值不超过 1：Math.abs(height(root.left) - height(root.right)) <= 1
				(2) 根节点的左子树为平衡二叉树：isBalanced(root.left) == true
				(3) 根节点的右子树为平衡二叉树：isBalanced(root.right) == true
			*/
            return Math.abs(height(root.left) - height(root.right)) <= 1
                   && isBalanced(root.left) && isBalanced(root.right);
        }
    }
	
	//返回以 root 为根节点的树的高度
    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            return Math.max(height(root.left), height(root.right)) + 1;
        }
    }
}

总结

本题的解法涉及了递归的应用，通过判断根节点的左右子树的高度差是否不超过 1，并且递归判断左右子树是否也是平衡二叉树，来确定整棵树是否为平衡二叉树。希望这个解题思路对你有所帮助。

#LeetCode 9