117. Populating Next Right Pointers in Each Node II

117. Populating Next Right Pointers in Each Node II

Follow up for problem “Populating Next Right Pointers in Each Node”.

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

You may only use constant extra space. For example, Given the following binary tree,

1 / \ 2 3 / \ \ 4 5 7

After calling your function, the tree should look like:

1 -> NULL / \ 2 -> 3 -> NULL / \ \ 4-> 5 -> 7 -> NULL

复杂度：时间 O(N) 空间 O(1)

思路： 第一问层次递进的延伸。上一问中我们不需要一个额外的指针来控制我们一层中链接的节点，因为我们知道肯定是左右左右的顺序，而这题中左右节点可能不存在，所有我们要用一个指针记录这一层中我们链接到了哪个节点，方便我们链接下一个节点。

/** * Definition for binary tree with next pointer. * public class TreeLinkNode { * int val; * TreeLinkNode left, right, next; * TreeLinkNode(int x) { val = x; } * } */public class Solution { public void connect(TreeLinkNode root) { // head是上一层的节点，我们用上一层节点的next形成链表，来链接当前这层 TreeLinkNode head = root; while(head != null){ // 记录链接到哪个节点的额外指针 TreeLinkNode curr = new TreeLinkNode(0); // tmp指向该层的第一节点 TreeLinkNode tmp = curr; while(head != null){ // 尝试链接左节点 if(head.left != null){ curr.next = head.left; curr = curr.next; } // 尝试链接右节点 if(head.right != null){ curr.next = head.right; curr = curr.next; } head = head.next; } // 将head移动到当前这层的的第一个，准备链接下一层 head = tmp.next; } }}

/** * Definition for binary tree with next pointer. * public class TreeLinkNode { * int val; * TreeLinkNode left, right, next; * TreeLinkNode(int x) { val = x; } * } */public class Solution { public Node connect(Node root) { LinkedList q = new LinkedList<>(); q.addLast(root); q.addLast(null); while(!q.isEmpty() && q.peekFirst() != null) { while(q.peekFirst() != null) { Node tmp = q.pollFirst(); tmp.next = q.peekFirst(); if(tmp.left != null) { q.addLast(tmp.left); } if(tmp.right != null) { q.addLast(tmp.right); } } q.pollFirst(); q.addLast(null); } return root; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。