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

在Populating Next Right Pointers in Each Node問題的基礎上，難度20，方法一樣。都是類似Binary Tree Level Order Traverse，都是把樹看成一個無向圖，然后用BFS的方式，需要記錄每一層的ParentNumInQueue以及ChildNumInQueue, 初始值為1和0，以后每次ParentNumInQ減至0說明這一層已經遍歷完畢，這一層的Child數將成為下一層的ParentNumInQ

1 /** 2 * Definition for binary tree with next pointer. 3 * public class TreeLinkNode { 4 * int val; 5 * TreeLinkNode left, right, next; 6 * TreeLinkNode(int x) { val = x; } 7 * } 8 */ 9 public class Solution { 10 public void connect(TreeLinkNode root) { 11 if (root == null) return; 12 LinkedList<TreeLinkNode> queue = new LinkedList<TreeLinkNode>(); 13 queue.add(root); 14 int ParentNumInQ = 1; 15 int ChildNumInQ = 0; 16 TreeLinkNode pre = null; 17 while (!queue.isEmpty()) { 18 TreeLinkNode cur = queue.poll(); 19 ParentNumInQ--; 20 if (pre == null) { 21 pre = cur; 22 } 23 else { 24 pre.next = cur; 25 pre = pre.next; 26 } 27 if (cur.left != null) { 28 queue.add(cur.left); 29 ChildNumInQ++; 30 } 31 if (cur.right != null) { 32 queue.add(cur.right); 33 ChildNumInQ++; 34 } 35 if (ParentNumInQ == 0) { 36 ParentNumInQ = ChildNumInQ; 37 ChildNumInQ = 0; 38 pre.next = null; 39 pre = null; 40 } 41 } 42 } 43 }

?

?

層次遞進法

復雜度

時間 O(N) 空間 O(1)

1 public class Solution { 2 3 //based on level order traversal 4 public void connect(TreeLinkNode root) { 5 6 TreeLinkNode head = null; //head of the next level 7 TreeLinkNode prev = null; //the leading node on the next level 8 TreeLinkNode cur = root; //current node of current level 9 10 while (cur != null) { 11 12 while (cur != null) { //iterate on the current level 13 //left child 14 if (cur.left != null) { 15 if (prev != null) { 16 prev.next = cur.left; 17 } else { 18 head = cur.left; 19 } 20 prev = cur.left; 21 } 22 //right child 23 if (cur.right != null) { 24 if (prev != null) { 25 prev.next = cur.right; 26 } else { 27 head = cur.right; 28 } 29 prev = cur.right; 30 } 31 //move to next node 32 cur = cur.next; 33 } 34 35 //move to next level 36 cur = head; 37 head = null; 38 prev = null; 39 } 40 41 } 42 }

?

轉載于:https://www.cnblogs.com/EdwardLiu/p/3978460.html

總結

以上是生活随笔為你收集整理的Leetcode: Populating Next Right Pointers in Each Node II的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。