首页 > 代码库 > [LeetCode]Populating Next Right Pointers in Each Node

[LeetCode]Populating Next Right Pointers in Each Node

题目:给定一颗完全二叉树,连接每个节点的next为该节点的右边同一层的节点

例如:

Given the following perfect binary tree,

         1
       /        2    3
     / \  /     4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL
       /        2 -> 3 -> NULL
     / \  /     4->5->6->7 -> NULL
算法:

将根节点压入队列中
若队列不为空,则执行循环
	取出并弹出队列首节点
	if 队列不为空
	then
		if 当前节点和队列队首节点位于二叉树的同一层
		then current_node.next = next_node
		end
	end
	将当前节点的左孩子和右孩子压入队尾
/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
       /**
		 * Algorithm:
		 * 
		 * 1. push root into queue
		 * while queue is not empty
		 *     2. get and pop the top tree node from queue
		 *     3. if queue has any tree node more
		 *         4. if current_node and next_node at the same depth
		 *         5. then current_node.next = next_node
		 *     6. push current.node.left and current_node.right into queue
		 * 
		 */
	    public void connect(TreeLinkNode root) {
	    	if (null == root) {
	    		// Empty Tree
	    		return ;
	    	}
	    	
	        int counter = 0;  // means the ith node of the tree
	    	Queue<TreeLinkNode> queue = new LinkedList<TreeLinkNode>();
	        queue.add(root);
	        while (!queue.isEmpty()) {
	        	TreeLinkNode node = queue.poll();
	        	++counter;
	        	if (!queue.isEmpty()) {
	        		int curDepth = (int)(Math.log(1.0*counter)/Math.log(2.0));
	        		int nextDepth = (int)(Math.log(1.0*counter+1.0)/Math.log(2.0));
	        		if (curDepth == nextDepth) {
	        			TreeLinkNode nextNode = queue.peek();
	        			node.next = nextNode;
	        		}
	        	}
	        	
        		if (null != node.left) {
        			queue.add(node.left);
        		}
        		if (null != node.right) {
        			queue.add(node.right);
        		}
	        }
	    }
}