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:
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
Solution:
/** * 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) { if (root==null) return; root.next = null; TreeLinkNode levelHead = root; while (true){ boolean hasChild = false; TreeLinkNode cur = levelHead; TreeLinkNode nextLevelPre = null; TreeLinkNode nextLevelHead = null; while (cur!=null){ if (cur.left!=null){ hasChild = true; if (nextLevelPre!=null){ nextLevelPre.next = cur.left; nextLevelPre = cur.left; } else { nextLevelPre = cur.left; nextLevelHead = cur.left; } } if (cur.right!=null){ hasChild = true; if (nextLevelPre!=null){ nextLevelPre.next = cur.right; nextLevelPre = cur.right; } else { nextLevelPre = cur.right; nextLevelHead = cur.right; } } cur = cur.next; } if (hasChild) nextLevelPre.next = null; //If reach the last level, then stop. if (!hasChild) break; //Move to next level. levelHead = nextLevelHead; } return; } }
At each level, after we construct the link list, we have a linked list to visit all nodes in this level. Then we can visit all child nodes in the next level along this linked list.This is a very smart way.
Note: For this question, we need to be careful about where the first child node in the next level is.
Leetcode-Populating Next Right Pointer in Binary Tree II
原文：http://www.cnblogs.com/lishiblog/p/4082949.html