首页 > 代码库 > [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); } } } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。