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

目录

• Leetcode 116 填充每个节点的下一个右侧节点
  • 方法1: 层序遍历(O(N)时间复杂度，O(N)空间复杂度)
  • 方法2: 利用已有的next指针(O(N)时间复杂度，O(1)空间复杂度)

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

将一个完美二叉树中每一个节点中的next指针指向同层右侧相邻节点，没有则指向null

方法1: 层序遍历(O(N)时间复杂度，O(N)空间复杂度)

执行用时：4 ms, 在所有 Java 提交中击败了20.62%的用户
内存消耗：40.2 MB, 在所有 Java 提交中击败了19.29%的用户

class Solution {
    //层序遍历，每层内设置next指针执行右边一个节点
    public Node connect(Node root) {
        if(root==null) {
            return root;
        }
        int currNodesNum = 1, nextNodesNum = 0;
        Queue<Node> nodeQueue = new LinkedList<>();
        Node peek = null;
        nodeQueue.offer(root);
        while(!nodeQueue.isEmpty()) {
            //取出两个节点
            peek = nodeQueue.poll();
            currNodesNum--;
            peek.next = (currNodesNum==0)?null:nodeQueue.peek();
            //添加下层节点
            if(peek.left!=null) {
                nodeQueue.offer(peek.left);
                nextNodesNum++;
            }
            if(peek.right!=null) {
                nodeQueue.offer(peek.right);
                nextNodesNum++;
            }
            //层交替
            if(currNodesNum==0) {
                currNodesNum = nextNodesNum;
                nextNodesNum = 0;
            }
        }
        return root;
    }
}

方法2: 利用已有的next指针(O(N)时间复杂度，O(1)空间复杂度)

class Solution {
    public Node connect(Node root) {
        
        if (root == null) {
            return root;
        }
        
        // Start with the root node. There are no next pointers
        // that need to be set up on the first level
        Node leftmost = root;
        
        // Once we reach the final level, we are done
        while (leftmost.left != null) {
            
            // Iterate the "linked list" starting from the head
            // node and using the next pointers, establish the 
            // corresponding links for the next level
            Node head = leftmost;
            
            while (head != null) {
                
                // CONNECTION 1
                head.left.next = head.right;
                
                // CONNECTION 2
                if (head.next != null) {
                    head.right.next = head.next.left;
                }
                
                // Progress along the list (nodes on the current level)
                head = head.next;
            }
            
            // Move onto the next level
            leftmost = leftmost.left;
        }
        
        return root;
    }
}