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

Bertha 。 2022-10-23 12:54 111阅读 0赞

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

//递归写法：把左子树的所有靠右边的节点的next指向右子树的所有靠左边的节点
    //https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/solution/cdi-gui-jian-dan-yi-dong-by-ting-yu-8t/
    /*
    // 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;
            }
            dfs(root);
            return root;
        }
        private void dfs(Node root){
        
            if(root.left == null && root.right == null)
                return;
            Node l = root.left;
            Node r = root.right;
            while(l != null){
        
                l.next = r;
                l = l.right;
                r = r.left;
            }
            dfs(root.left);
            dfs(root.right);
        }
    }

//写法二：类似于层次遍历：遍历这一层节点组织成的链表，为下一层的节点更新 next 指针
    //https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/solution/tian-chong-mei-ge-jie-dian-de-xia-yi-ge-you-ce-2-4/
    /*
    // 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 root;
            }
            Node leftmost = root;
            while(leftmost.left != null){
        
                Node head = leftmost;
    
                while(head != null){
        
                    head.left.next = head.right;
                    if(head.next != null){
        
                        head.right.next = head.next.left;
                    }
                    head = head.next;
                }
                leftmost = leftmost.left;
            }
            return root;
        }
    }

//利用队列的层次遍历
    //https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/solution/tian-chong-mei-ge-jie-dian-de-xia-yi-ge-you-ce-2-4/
    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;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20221023/6444c8eb90194605ba64dd94b64f9dab.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70 1]: /images/20221023/be2e3dab88714b47ad2765f330597c55.png