Leetcode BinaryTree 116, 117 @ Java－CONY的世界

116. Populating Next Right Pointers in Each Node

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,

After calling your function, the tree should look like:

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

注意這題的需求

1. use only extra constant space ----> cann't use resursive. use iterative to do the recursive work

2.perfect binary tree --> each nonleaf node has two child

這題基本上就是一個node做好兩件事情，

1. 把自己的 left child next 跟 right child 接好

2.如果自己有next，就把right child next 也跟自己的next.left接好

然後一層一層做就可以了

/**
 * 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) {
        TreeLinkNode next = root, cur;
        if(root != null) { 
            while(next.left != null) {
                cur = next;
                while(cur != null) {
                    cur.left.next = cur.right;
                    if(cur.next != null)    cur.right.next = cur.next.left;
                    cur = cur.next;
                }
                next = next.left;
            }
        }
    }
}

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,

After calling your function, the tree should look like:

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

不是perfect binary tree後，就無法再確定next.left 是否依定會存在了

所以要在每個child時判斷是否設定了，然後set

然後因為不是 perfect binary 表示我們無法確定cur child 的next會在哪裡，所以只能先將cur child 先存在prev

然後如果走到存在的next child node時再去把previous.next 設起來，並且同時更新 cur child 到prev 繼續等待下一個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 void connect(TreeLinkNode root) {
        if(root == null)    return;
        TreeLinkNode next = root, cur, prev=null;
        while(next != null) {
            cur = next;
            next= null; prev=null;
            while(cur != null){
                if(cur.left != null) {
                    if(prev != null)
                        prev.next = cur.left;
                    else
                        next = cur.left;
                    prev = cur.left;
                }
                if(cur.right != null) {
                    if(prev != null)
                        prev.next = cur.right;
                    else
                        next = cur.right;
                    prev = cur.right;
                }
                cur = cur.next;
            }
        }
    }
}