[LeetCode 中等 二叉树+链表]117. 填充每个节点的下一个右侧节点指针 II

题目描述

117. 填充每个节点的下一个右侧节点指针 II
     给定一个二叉树

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

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

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

进阶：

你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

示例：

输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。

提示：

树中的节点数小于 6000-100 <= node.val <= 100

queu 空间复杂度是最大层的节点个数

每一次queue的size就是 层里的节点数

class Solution {
    public Node connect(Node root) {
        if(root == null) return root;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int n = queue.size();
            for (int i = 1; i <= n; ++i) {
                Node curr = queue.poll();
                if (curr.left != null) {
                    queue.offer(curr.left);
                }
                if (curr.right != null) {
                    queue.offer(curr.right);
                }
                if (i != n) {
                    curr.next = queue.peek();
                }
            }
        }

        return root;
       
    }
}

空间复杂度：O(1)

/*
// 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;
    }
};
*/

class Solution {
Node last = null, nextStart = null;

    public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        Node start = root;
        //  start 代表往后读所有的节点
        while (start != null) {
            //用来生成链表 
            last = null;
            //就是一个层的最左边的节点 （也是循环开始的节点）
            //在操作中会把每一层读成一个链表    
            nextStart = null;
            for (Node p = start; p != null; p = p.next) {
                if (p.left != null) {
                    handle(p.left);
                }
                if (p.right != null) {
                    handle(p.right);
                }
            }
            start = nextStart;
        }
        return root;
    }
//  
    public void handle(Node p) {
        //初始化 如果是空 就往后加
        if (last != null) {
            last.next = p;
        }
        
        if (nextStart == null) {
            nextStart = p;
        }
        //下一个要进行操作的node
        last = p;
    }
}