BM36-判断是不是平衡二叉树

题目

输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。

在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

样例解释：

样例二叉树如图，为一颗平衡二叉树

注：我们约定空树是平衡二叉树。

数据范围：n≤100,树上节点的val值满足 0≤n≤1000

要求：空间复杂度O(1)，时间复杂度O(n)

输入描述：输入一棵二叉树的根节点

返回值描述：输出一个布尔类型的值

示例1

输入：{1,2,3,4,5,6,7}

返回值：true

示例2

输入：{}

返回值：true

思路

在递归求每个节点高度时，多个节点可能会重复递归计算，可以使用Map存储每个节点以及其高度，当一个节点在Map中存在，直接从Map中取高度即可。

代码

import java.util.*;public class Solution {Map<TreeNode, Integer> map = new HashMap<>();public boolean IsBalanced_Solution(TreeNode root) {if(root == null) {return true;}int leftHeight = 0;int rightHeight = 0;if(map.containsKey(root.left)) {leftHeight = map.get(root.left);} else {leftHeight = height(root.left);map.put(root.left, leftHeight);}if(map.containsKey(root.right)) {rightHeight = map.get(root.right);} else {rightHeight = height(root.right);map.put(root.right, rightHeight);}int heightAbs = Math.abs(leftHeight - rightHeight);if(heightAbs > 1) {return false;}return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);}public int height(TreeNode root) {if(root == null) {return 0;}return 1 + Math.max(height(root.left), height(root.right));}
}