java两种方法(有Map以及无Map)求二叉树最大宽度

  • 时间:
  • 浏览:
  • 来源:互联网

有Map法

思路

这个首先要有bfs的思路,如果不会bfs可以先学习bfs

  • 根据真题学习bfs

有Map方法的思路就是,key值保存Node节点,value保存该节点在哪一层。从head开始入队,左右节点不为空就入队,然后给节点设置value,我们是用上一层父节点设置的,所以子节点层数为本次层数+1。如果层数==记录节点的层数,那么记录的宽度就+1,不等于的时候也就是到了下一层,然后设置变量:宽度设置为0,层数++,max与宽度作比较一下,大的给max。最后遍历完了不会记录最后一层下一层的节点,所以不会走到最后的else,因而最后return的时候需要再做一下比较,返回较大的宽度

代码

public static int maxWidthUseMap(Node head) {
	if(head==null) {
		return 0;
	}
	Queue<Node> queue = new LinkedList<>();
	queue.add(head);
	//value:在哪一层,key存放节点
	HashMap<Node,Integer> levelMap=new HashMap<>();
	levelMap.put(head, 1);
	int curLevel=1;//当前在统计哪一层的宽度
	int curLevelNodes=0;//当前层curLevel层,宽度目前是多少
	int max=0;
	while(!queue.isEmpty()) {
		Node cur=queue.poll();
		int curNodeLevel=levelMap.get(cur);
		if(cur.left!=null) {
			levelMap.put(cur.left,curNodeLevel+1);
			queue.add(cur.left);
		}
		if(cur.right!=null) {
			levelMap.put(cur.right, curNodeLevel+1);
			queue.add(cur.right);
		}
		
		if(curNodeLevel==curLevel) {
			curLevelNodes++;
		}else {
			max=Math.max(max, curNodeLevel);
			curLevel++;
			curLevelNodes=1;
		}
	}
	return Math.max(max, curLevelNodes);
}

无Map法

思路

个人觉得无Map法甚至理解起来更加容易。思路是这样的,用curEnd表示这一层最右边的节点,什么是最右边的节点呢,就是一层一层的看二叉树,每一层都会有最右边的一个节点,这里我们用curEnd表示,用nextEnd表示下一层的最右边的节点。if判断,从左到右更新curEnd,并且每更新一次就让宽度(curLevelNodes)++, 最后直接返回max即可

代码

public static int maxWidthNoMap(Node head) {
	if(head==null) {
		return 0;
	}
	Queue<Node> queue = new LinkedList<>();
	queue.add(head);
	Node curEnd=head;//当前层的最右节点
	Node nextEnd=null;//下一层的最右节点
	int max=0;
	int curLevelNodes=0;//当前层的节点数
	while(!queue.isEmpty()) {
		Node cur=queue.poll();
		if(cur.left!=null) {
			queue.add(cur.left);
			nextEnd=cur.left;
		}
		if(cur.right!=null) {
			queue.add(cur.right);
			nextEnd=cur.right;
		}
		curLevelNodes++;
		if(cur==curEnd) {
			max=Math.max(max, curLevelNodes);
			curLevelNodes=0;
			curEnd=nextEnd;
		}
	}
	return max;
}

本文链接http://www.dzjqx.cn/news/show-617020.html