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

r囧r小猫 2022-12-23 03:30 112阅读 0赞

# 题目来源 #

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

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]

# 题目解析 #

## 队列 ##

![在这里插入图片描述][20201122131946694.gif_pic_center]

/*
    // 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();
                for (int i = 0; i < size; i++){
        
                    Node pop = queue.poll();
                    if (i < size - 1){
        
                        pop.next = queue.peek();
                    }
                    if (pop.left != null){
        
                        queue.offer(pop.left);
                    }
                    if (pop.right != null){
        
                        queue.offer(pop.right);
                    }
                }
            }
            
            return root;
        }
    
    }

## 递归 ##

![在这里插入图片描述][20201122130507663.gif_pic_center]

/*
    // 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;
            }
    
            Node left = root.left;
            Node right = root.right;
            while (left != null){
        
                left.next = right;
                left = left.right;
                right = right.left;
            }
            
            connect(root.left);
            connect(root.right);
            
            return root;
        }
    
    }

## 递归 ##

*  每个node左子树的next，就是node的右子树
 *  每个node右子树的next。就是node.next的左子树

[116.]: https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/35f829eaf1a74e76b18fa9f9dd8cc5ea.png
[20201122131946694.gif_pic_center]: https://img-blog.csdnimg.cn/20201122131946694.gif#pic_center
[20201122130507663.gif_pic_center]: https://img-blog.csdnimg.cn/20201122130507663.gif#pic_center