[LeetCode每日一题]116. Populating Next Right Pointers in Each Node

题目如下：

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *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.

116. Populating Next Right Pointers in Each Node
一个例子如下图所示：

第一个想到的方法是BFS，从根节点开始逐层编号，根节点编号为1，给定的二叉树是满二叉树，所以next需要指向null的节点都是有特点的，它们的编号满足下面的条件：

编号 + 1 == 2的k次幂

不妨设节点编号为count，设k为exp，实现代码如下：

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        double count = 0;
        int exp = 1;
        Queue<Node> queue = new LinkedList();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            count++;
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            if (Math.pow(2, exp) - 1 == count) {
                node.next = null;
                exp++;
            } else {
                node.next = queue.peek();
            }
        }
        return root;
    }
}

另一个更好的办法是通过递归，实现代码如下：

class Solution {
    public Node connect(Node root) {
        connectNode(root, null);
        return root;
    }

    private void connectNode(Node currentNode, Node nextNode) {
        if (currentNode == null) {
            return;
        }
        currentNode.next = nextNode;
        connectNode(currentNode.left, currentNode.right);
        Node node = currentNode.next == null ? null : currentNode.next.left;
        connectNode(currentNode.right, node);
        return;
    }
}