117.Populating-Next-Right-Pointers-in-Each-Node-II

117. Populating Next Right Pointers in Each Node II

题目地址

https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/

题目描述

Given a binary tree

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Follow up:
You may only use constant extra space.
Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem.

Example 1:
Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Constraints:
The number of nodes in the given tree is less than 6000.
-100 <= node.val <= 100

代码

Approach 1: BFS Level Order Traversal

Time Complexity: O(N) & Space Complexity: O(N)

class Solution {
  public Node connect(Node root) {
        if (root == null) return root;

    Queue<Node> queue = new LinkedList<Node>();
    queue.add(root);

    while (queue.size() > 0) {
      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;
  }
}
/*
// 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;
    }
};
*/

Approach #2

public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) return;
        TreeLinkNode curP = root;
        TreeLinkNode nextDummyHead = new TreeLinkNode(0);
        TreeLinkNode p = nextDummyHead;
        while (curP != null) {
            if (curP.left != null) {
                p.next = curP.left;
                p = p.next;
            }
            if (curP.right != null) {
                p.next = curP.right;
                p = p.next;
            }

            if (curP.next != null) {
                curP = curP.next;
            } else {
                curP = nextDummyHead.next;
                nextDummyHead.next = null;
                p = nextDummyHead;
            }
        }
    }
}

//Another version with two while loops, but with same performance, and the meaning is clearer...
public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) return;
        TreeLinkNode dummy = new TreeLinkNode(0);
        TreeLinkNode p = dummy;
        TreeLinkNode head = root;
        while (head != null) { //if the head of the traverse layer is not null, then traverse that layer...
            TreeLinkNode node = head;
            while (node != null) {
                if (node.left != null) {
                    p.next = node.left;
                    p = p.next;
                }
                if (node.right != null) {
                    p.next = node.right;
                    p = p.next;
                }
                node = node.next;
            }
            //after traversed to the end of current layer, move to the next layer
            head = dummy.next;
            dummy.next = null;
            p = dummy;
        }
    }
}

Approach #2 Using previously established next pointers

Time Complexity: O(N) & Space Complexity: O(1)

class Solution {
    Node prev, leftmost;

    public Node connect(Node root) {
        if (root == null) {
            return root;
        }
        // The root node is the only node on the first level
        // and hence its the leftmost node for that level
        this.leftmost = root;
        // Variable to keep track of leading node on the "current" level
        Node curr = leftmost;
        // We have no idea about the structure of the tree,
        // so, we keep going until we do find the last level.
        // the nodes on the last level won't have any children
        while (this.leftmost != null) {
            // "prev" tracks the latest node on the "next" level
            // while "curr" tracks the latest node on the current
            // level.
            this.prev = null;
            curr = this.leftmost;
            // We reset this so that we can re-assign it to the leftmost
            // node of the next level. Also, if there isn't one, this
            // would help break us out of the outermost loop.
            this.leftmost = null;
            // Iterate on the nodes in the current level using
            // the next pointers already established.
            while (curr != null) {
                // Process both the children and update the prev
                // and leftmost pointers as necessary.
                this.processChild(curr.left);
                this.processChild(curr.right);
                // Move onto the next node.
                curr = curr.next;
            }
        }

        return root ;
    }

      public void processChild(Node childNode) {
        if (childNode != null) {
            // If the "prev" pointer is alread set i.e. if we
            // already found atleast one node on the next level,
            // setup its next pointer
            if (this.prev != null) {
                this.prev.next = childNode;
            } else {
                // Else it means this child node is the first node
                // we have encountered on the next level, so, we
                // set the leftmost pointer
                this.leftmost = childNode;
            }    
            this.prev = childNode; 
        }
    }
}