116. 填充每个节点的下一个右侧节点指针（中等）

忘是亡心i 2022-09-10 05:24 126阅读 0赞

Leetcode链接：[116. 填充每个节点的下一个右侧节点指针][116.]

### 题目描述 ###

> 给定一个 `完美二叉树（完全二叉树）` ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：  
>   
>   
> struct Node \{  
> int val;  
> Node \*left;  
> Node \*right;  
> Node \*next;  
> \}  
>   
>   
> 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 `NULL`。  
>   
>   
> 初始状态下，所有 next 指针都被设置为 `NULL`。

进阶：

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

示例：

> 输入：root = \[1,2,3,4,5,6,7\]  
> 输出：\[1,\#,2,3,\#,4,5,6,7,\#\]  
> 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，’\#’ 标志着每一层的结束。

提示：

> 树中节点的数量少于 4096  
> \-1000 <= node.val <= 1000

##### 官方处理方式 #####

*  利用队列的peek节点

class Solution {
        
        public Node connect(Node root) {
        
            if (root == null) {
        
                return root;
            }
            
            // 初始化队列同时将第一层节点加入队列中，即根节点
            Queue<Node> queue = new LinkedList<Node>(); 
            queue.add(root);
            
            // 外层的 while 循环迭代的是层数
            while (!queue.isEmpty()) {
            
                // 记录当前队列大小
                int size = queue.size();     
                // 遍历这一层的所有节点
                for (int i = 0; i < size; i++) {
        
                    
                    // 从队首取出元素
                    Node node = queue.poll();
                    
                    // 连接
                    if (i < size - 1) {
        
                        node.next = queue.peek();
                    }
                    
                    // 拓展下一层节点
                    if (node.left != null) {
        
                        queue.add(node.left);
                    }
                    if (node.right != null) {
        
                        queue.add(node.right);
                    }
                }
            }
            // 返回根节点
            return root;
        }
    }

##### 链表处理方式 – 个人方法 #####

*  利用curr头结点链式处理

/*
    // 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 {
        
        public Node connect(Node root) {
        
            if(root == null) return null;
            Queue<Node> queue = new LinkedList<>();
            queue.offer(root);
            while(!queue.isEmpty()){
        
                int size = queue.size();
                //链表处理方式
                Node curr = new Node(0);
                for(int i = 0; i < size; i++){
        
                    Node node = queue.poll();
                    //链接
                    curr.next = node;
                    curr = curr.next;
                    if(node.left != null){
        
                        queue.offer(node.left);
                    }
                    if(node.right != null){
        
                        queue.offer(node.right);
                    }
                }
            }
            return root;
        }
    }

[116.]: https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/