【leetcode】No.117：populating-next

题目描述

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

思路

将树与链表结合起来的一道题，在第一层的时候通过left与right将第二层的节点连接起来，在第二层又连接第三层，那么如何将从第一层到第二层呢，用队列空间复杂度不合要求，所以可以考虑使用头节点来连接链表，可以顺理成章的从链表的头结点顺着遍历第二层的节点。

代码

/**
 * 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) {
        while (root != null) {
            //创建一个头结点
            TreeLinkNode head = new TreeLinkNode(0);
            TreeLinkNode cur = head;
            while (root != null) {
                //将下一层节点连接成链表
                if (root.left != null){
                    cur.next = root.left;
                    cur = cur.next;
                }
                if (root.right != null){
                    cur.next = root.right;
                    cur = cur.next;
                }
                // 继续遍历下一个节点
                root = root.next;
            }
            // 如果遍历完该层，则从下一层的头结点下一个节点开始遍历
            root = head.next;
        }
    }
}