登录
  • #刷题
  • #careercup

问个复杂度。CC150上的判断一个树是否平衡

TonyJang
1081
3
package bianryTree;[br][/br][br][/br]public class treeBalanced {[br][/br][br][/br]public static int getHeight(Node root){[br][/br][br][/br]	if(root==null) return 0;[br][/br][br][/br]	[br][/br][br][/br]	return (Math.max(getHeight(root.getLeft()),getHeight(root.getRight())+1));[br][/br][br][/br]}[br][/br][br][/br]	[br][/br][br][/br]public static boolean isBalanced(Node root){[br][/br][br][/br]	if(root==null) return true;[br][/br][br][/br]	[br][/br][br][/br]	int diff=getHeight(root.getLeft())-getHeight(root.getRight());[br][/br][br][/br]	if(Math.abs(diff)>1){[br][/br][br][/br]		return false;[br][/br][br][/br]		[br][/br][br][/br]	}else{[br][/br][br][/br]		[br][/br][br][/br]		return isBalanced(root.getLeft())&&isBalanced(root.getRight());[br][/br][br][/br]		[br][/br][br][/br]	}[br][/br][br][/br]	[br][/br][br][/br]	[br][/br][br][/br]}[br][/br][br][/br]	[br][/br][br][/br]}[br][/br][br][/br]
getHeight递归调用所有的节点为O(N),isBalanced也是O(N),嵌套进去应该是O(N×N)吧,为什么答案写的是O(N×log(N))?
3条回复
热度排序

发表回复