leetcode 116填充每个节点的下一个右侧节点

小咪咪 2023-06-18 06:56 7阅读 0赞

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node \{  
int val;  
Node \*left;  
Node \*right;  
Node \*next;  
\}  
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

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

示例：

输入：\{"$id":"1","left":\{"$id":"2","left":\{"$id":"3","left":null,"next":null,"right":null,"val":4\},"next":null,"right":\{"$id":"4","left":null,"next":null,"right":null,"val":5\},"val":2\},"next":null,"right":\{"$id":"5","left":\{"$id":"6","left":null,"next":null,"right":null,"val":6\},"next":null,"right":\{"$id":"7","left":null,"next":null,"right":null,"val":7\},"val":3\},"val":1\}

输出：\{"$id":"1","left":\{"$id":"2","left":\{"$id":"3","left":null,"next":\{"$id":"4","left":null,"next":\{"$id":"5","left":null,"next":\{"$id":"6","left":null,"next":null,"right":null,"val":7\},"right":null,"val":6\},"right":null,"val":5\},"right":null,"val":4\},"next":\{"$id":"7","left":\{"$ref":"5"\},"next":null,"right":\{"$ref":"6"\},"val":3\},"right":\{"$ref":"4"\},"val":2\},"next":null,"right":\{"$ref":"7"\},"val":1\}

解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。

**提示：**

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

思路1： bfs 不断连接

/*
    // 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.add(root);
    
            while (!queue.isEmpty()) {
                int size = queue.size();
                Node pn = null;
                while (size-- >0) {
                    Node node = queue.poll();
                    if (node.left !=null)
                        queue.add(node.left);
                    if (node.right != null)
                        queue.add(node.right);
                    if (pn != null) {
                        pn.next = node;
                        pn = node;
                    } else {
                        pn = node;
                    }
                }
    
            }
            return root;
    
        }
    }

思路2: 递归的操作，原来还能这样操作，第一次感觉递归这样玩

public Node connect(Node root) {
            if (root == null)return null;
            if (root.left !=null) {
                root.left.next = root.right;
                if (root.next != null && root.right !=null) {
                    root.right.next = root.next.left;
                }
            }
    
            connect(root.left);
            connect(root.right);
            return root;
        }

思路3： 迭代的形式

public Node connect(Node root) {
           
           Node pre = root;
           while (pre != null) {
               Node now = pre;
               while (now != null) {
                   if (now.left != null) {
                       now.left.next = now.right;
                   }
                   if (now.right !=null && now.next!=null) {
                       now.right.next = now.next.left;
                   }
                   now = now.next;
               }
               pre = pre.left;
           }
           
    
            return root;
        }