/**
*
* Source : https://oj.leetcode.com/problems/populating-next-right-pointers-in-each-node/
* Source : https://oj.leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/
*
*
*
* Given a binary tree
*
* struct TreeLinkNode {
* TreeLinkNode *left;
* TreeLinkNode *right;
* TreeLinkNode *next;
* }
*
* Populate each next pointer to point to its next right node.
* If there is no next right node, the next pointer should be set to NULL.
*
* Initially, all next pointers are set to NULL.
*
* Note:
*
* You may only use constant extra space.
* You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
*
* For example,
* 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
*
* 下面是II，如果是一般二叉树而不是特殊的完全二叉树，求解，因为适合II的解同样可以解决问题I，这里直接解决问题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
*
*/
public class PopulatingNextRightPointers {
/**
*
* 将二叉树的每一层节点连接成为一个单向链表
*
* 假设当前层已经连接好，那么下一层怎么连接？
* 从当前层的最左节点开始
* 如果当前根节点root的左右子树都为空，则直接向后移动一个节点
*
* leftMost = root.left != null ? root.left : root.right
* cur = leftMost
*
* 循环当前一层的所有节点，知道2下一个节点为空，说明当前层循环完
* 左右子树中至少有一个，：
* 如果cur==左子树，如果右子树不为空则将cur.next = root.right，且将cur和root向后移，cur = cur.next,root = root.next
* 如果cur == 右子树，直接将根节点向后移root = root.next
* 如果cur和左右子树都不相同，则说明cur属于上一个根节点的子节点
* 如果当前根节点的左右子节点都为空，根节点向后移
* 否则更新cur，cur = root.left != null ? root.left : root.right,cur = cur.next
*
* 对下一层（上面已经连接成链表）进行递归
*
* @param root
* @return
*/
public TreeLinkedNode populate (TreeLinkedNode root) {
// 没有子节点，将当前层向后移动一个
while (root != null && root.leftChild == null && root.rightChild == null) {
root = root.next;
}
if (root == null) {
return null;
}
TreeLinkedNode leftMost = root.leftChild != null ? root.leftChild : root.rightChild;
TreeLinkedNode cur = leftMost;
while (root != null) {
if (cur == root.leftChild) {
if (root.rightChild != null) {
cur.next = root.rightChild;
cur = cur.next;
}
root = root.next;
} else if (cur == root.rightChild) {
root = root.next;
} else {
if (root.leftChild == null && root.rightChild == null) {
root = root.next;
} else {
cur.next = root.leftChild != null ? root.leftChild : root.rightChild;
cur = cur.next;
}
}
}
populate(leftMost);
return root;
}
public TreeLinkedNode populateByIterator (TreeLinkedNode root) {
TreeLinkedNode leftMost = root;
while (leftMost != null) {
root = leftMost;
// 没有子节点，将当前层向后移动一个
while (root != null && root.leftChild == null && root.rightChild == null) {
root = root.next;
}
if (root == null) {
return null;
}
leftMost = root.leftChild != null ? root.leftChild : root.rightChild;
TreeLinkedNode cur = leftMost;
while (root != null) {
if (cur == root.leftChild) {
if (root.rightChild != null) {
cur.next = root.rightChild;
cur = cur.next;
}
root = root.next;
} else if (cur == root.rightChild) {
root = root.next;
} else {
if (root.leftChild == null && root.rightChild == null) {
root = root.next;
} else {
cur.next = root.leftChild != null ? root.leftChild : root.rightChild;
cur = cur.next;
}
}
}
}
return root;
}
private class TreeLinkedNode {
int value;
TreeLinkedNode next;
TreeLinkedNode leftChild;
TreeLinkedNode rightChild;
public TreeLinkedNode(int value) {
this.value = value;
}
}
public TreeLinkedNode createTree (char[] treeArr) {
TreeLinkedNode[] tree = new TreeLinkedNode[treeArr.length];
for (int i = 0; i < treeArr.length; i++) {
if (treeArr[i] == '#') {
tree[i] = null;
continue;
}
tree[i] = new TreeLinkedNode(treeArr[i]-'0');
}
int pos = 0;
for (int i = 0; i < treeArr.length && pos < treeArr.length-1; i++) {
if (tree[i] != null) {
tree[i].leftChild = tree[++pos];
if (pos < treeArr.length-1) {
tree[i].rightChild = tree[++pos];
}
}
}
return tree[0];
}
public static void main(String[] args) {
PopulatingNextRightPointers nextRightPointers = new PopulatingNextRightPointers();
char[] arr = new char[]{'1','2','3','4','5','#','7'};
TreeLinkedNode root = nextRightPointers.createTree(arr);
nextRightPointers.populate(root);
root = nextRightPointers.createTree(arr);
nextRightPointers.populateByIterator(root);
}
}
