[leetcode-117]填充每个节点的下一个右侧节点指针 II

(1 AC)

填充每个节点的下一个右侧节点指针 I是完美二叉树。这个是任意二叉树

给定一个二叉树

struct Node {

  int val;

  Node *left;

  Node *right;

  Node *next;

}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

示例：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

关键：
层序遍历
Java中的队列：Queue<TreeLinkNode> queue = new LinkedList<>();

/**

 * Definition for binary tree with next pointer.

 * public class TreeLinkNode {

 *     int val;

 *     TreeLinkNode left, right, next;

 *     TreeLinkNode(int x) { val = x; }

 * }

 */

public class PopulatingNextRightPointersInEachNodeii {

    public void connect(TreeLinkNode root) {

        if (root == null) {

            return;

        }

        Queue<TreeLinkNode> queue = new LinkedList<>();

        queue.add(root);

        while(queue.size() != 0) {

            int size = queue.size(); // 当前层节点数

            TreeLinkNode node1 = queue.poll();

            if (node1.left != null)

            queue.add(node1.left);

            if (node1.right != null)

            queue.add(node1.right);

            for (int i=1;i<size;i++) {

                TreeLinkNode node2 = queue.poll();

                if (node2.left != null)

                queue.add(node2.left);

                if (node2.right != null)

                queue.add(node2.right);

                node1.next = node2;

                node1 = node2;

            }

        }

    }

}

[leetcode-117]填充每个节点的下一个右侧节点指针 II的相关教程结束。