自己建设网站要多久,公众号怎么做小程序,2015年全球网站优秀设计师,短视频营销推广题目
输入一棵节点数为 n 二叉树#xff0c;判断该二叉树是否是平衡二叉树。
在这里#xff0c;我们只需要考虑其平衡性#xff0c;不需要考虑其是不是排序二叉树
平衡二叉树#xff08;Balanced Binary Tree#xff09;#xff0c;具有以下性质#xff1a;它是一棵空…题目
输入一棵节点数为 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 {MapTreeNode, 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));}
}
