填充每个节点的下一个右侧节点指针[利用好每个点-＞尽可能降低时空复杂度]

前言

层次遍历是操作二叉树的基础遍历之一，通过在分层中做任何需求，完成分层遍历的各种变体。
除此之外，利用好每一个点/甚至是自己创造的点，尽可能的降低时空复杂度。有时利用给的数组和矩阵，原地修改，降低时空复杂度。

一、填充每个节点的下一个右侧节点指针

二、分层与利用next

1、分层遍历

// 完美二叉树
public class Connect {
    
    // 分层遍历即可
    public Node connect(Node root) {
    
        if (root == null) return null;
        Queue<Node> que = new LinkedList<>();
        que.offer(root);
        int size = que.size();
        Node pre = null;
        while (!que.isEmpty()) {
    
            Node cur = que.poll();
            if (cur.left != null) que.offer(cur.left);
            if (cur.right != null) que.offer(cur.right);
            if (pre != null) pre.next = cur;
            pre = cur;
            if (--size == 0) {
    
                size = que.size();
                pre = null;
            }
        }
        return root;
    }

    // Definition for a Node.
    class Node {
    
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {
    
        }

        public Node(int _val) {
    
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
    
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    }

    ;
}

2、利用已有的next

// 递归 + 额外常数空间。需要利用二叉树自身特性。
class Connect2 {
    
    // 利用已设置的next
    public Node connect(Node root) {
    
        if (root == null) return null;

        Node upDummy = new Node(0, null, null, root);
        Node downDummy = new Node();
        // 通过已有next+加上下层dummyHead,一层一层的设置next，循环下去。
        while (upDummy.next != null) {
    
            Node pUp = upDummy;
            Node pDown = downDummy;
            for (; pUp.next != null; pUp = pUp.next) {
    
                // 两个孩子都为空，下一层链表没什么赋值的。
                if (pUp.next.left == null && pUp.next.right == null) continue;
                // 两个孩子都有，则需要将两个孩子串联起来，并得到tail节点。
                if (pUp.next.left != null && pUp.next.right != null) {
    
                    // 串两个孩子
                    pUp.next.left.next = pUp.next.right;
                    // 将串好的两个孩子接到前面的链表后，即tail节点处。
                    pDown.next = pUp.next.left;
                    // 更新tail指针，为下一次cycle做准备。
                    pDown = pUp.next.right;
                } else {
    // 只有一个孩子的情况，不需要串，只需要把不为空的孩子接到tail处，再更新tail节点。
                    pDown.next = pUp.next.left == null ? pUp.next.right : pUp.next.left;
                    pDown = pDown.next;
                }
            }
            // update for next cycle
            upDummy = downDummy;
            downDummy = new Node();
        }
        // 返回原始的根节点。
        return root;
    }

    // Definition for a Node.
    class Node {
    
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {
    
        }

        public Node(int _val) {
    
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
    
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    }

    ;
}

总结

1）分层遍历。
2）利用好每个特别的地方，发挥它的价值，降低时空复杂度。

参考文献

[1] LeetCode 填充每个节点的下一个右侧节点指针