二叉树--链接下一个右侧节点优化

今天来优化下之前实现过的链接下一个右侧节点算法，同时将Ⅰ和Ⅱ做了合并。

题目介绍

给定任意一个二叉树，填充它的next节点，指向下一个右侧节点，最右侧节点指向null。

看下图吧：

二叉树-填充每个节点的下一个右侧节点指针Ⅱ-题目.png

实现思路

今天的实现思路是借助按层遍历树，同时又稍微做了调整。

核心思路为：
1.算法利用两个队列，一个当前层的节点队列，一个是下一层的节点队列。
2.每次遍历当前层队列，不断的从队列中取出元素，然后设置nent指向的节点。
3.另外将当前层的非空子节点加如到下一层的节点队列。
4.最终递归处理下一层的节点队列。

该算法的时间复杂度和空间复杂度都不是很好，只是换一种思维来实现而已。

实现代码

public class SolutionConnect2 {

    public Node connect(Node root) {
        if (null == root) {
            return null;
        }
        Queue<Node> currentQueue = new LinkedList<>();
        currentQueue.add(root);
        connect(currentQueue);

        return root;
    }

    private void connect(Queue<Node> currentQueue) {
        if (currentQueue.size() == 0) {
            return;
        }
        Queue<Node> childrenQueue = new LinkedList<>();
        Node leftMostNode = currentQueue.remove();
        while (null != leftMostNode) {
            if (leftMostNode.left != null) {
                childrenQueue.add(leftMostNode.left);
            }
            if (leftMostNode.right != null) {
                childrenQueue.add(leftMostNode.right);
            }

            Node node = null;
            if(currentQueue.size()>0){
                node = currentQueue.remove();
                leftMostNode.next = node;
            }
            leftMostNode = node;
        }
        connect(childrenQueue);
    }
}

算法相关实现源码地址：https://github.com/xiekq/rubs-algorithms