Populating Next Right Pointers in Each Node II

发表于   |   分类于 ，

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.

What if the given tree could be any binary tree?

Note:
You may only use constant extra space.

描述

给出一个任意的二叉树，使其每一个节点都指向右侧节点，并且不能使用额外的空间进行操作

分析

设置两个指针，分别指向相邻的两层，通过上层的节点，将下层的节点连接起来

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * 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 head = root;

        while (head != null) {

            TreeLinkNode up = head;
            TreeLinkNode down = new TreeLinkNode(0);
            TreeLinkNode go = down;

            while (up != null) {

                if (up.left != null) {
                    go.next = up.left;
                    go = go.next;
                }

                if (up.right != null) {
                    go.next = up.right;
                    go = go.next;
                }

                up = up.next;
            }

            head = down.next;
        }
    }
}