[116 Populating Next Right Pointers in Each Node] #leetcode

116_0803.py

# Definition for binary tree with next pointer.
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None

from collections import deque

class Solution:
    # @param root, a tree link node
    # @return nothing
    def connect(self, root):
        if root is None:
            return
        queue = deque([root, None])
        while not((len(queue) == 1 and queue[0] is None)):
            node = queue.popleft()
            if node is None:
                queue.append(None)
            else:
                node.next = queue[0]
                if node.left is not None:
                    queue.extend([node.left, node.right])
                    
class Solution1:
    # @param root, a tree link node
    # @return nothing
    def connect(self, root):
        if root is None:
            return 
        leftmost = root
        root.next = None
        while (leftmost and leftmost.left):
            cur = leftmost
            while (cur):
                cur.left.next = cur.right
                if (cur.next):
                    cur.right.next = cur.next.left
                else:
                    cur.right.next = None
                cur = cur.next
            leftmost = leftmost.left
            
class Solution2:
    # @param root, a tree link node
    # @return nothing
    def connect(self, root):
        if root is None:
            return 
        leftmost = root
        while (leftmost.left):
            cur = leftmost
            while (cur):
                cur.left.next = cur.right
                if (cur.next):
                    cur.right.next = cur.next.left
                cur = cur.next
            leftmost = leftmost.left

116_0804.java

public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) {
            return;
        }
        
        TreeLinkNode leftmost = root;
        TreeLinkNode cur = null;
        
        while (leftmost.left != null) {
            cur = leftmost;
            
            while (cur != null ) {
                cur.left.next = cur.right;
                if (cur.next != null) {
                    cur.right.next = cur.next.left;
                }
                cur = cur.next;
            }
            
            leftmost = leftmost.left;
        }
    }
}

public class Solution1 {
    public void connect(TreeLinkNode root) {
        if (root == null) {
            return;
        }
        
        if (root.left != null) {
            root.left.next = root.right;
            if (root.next != null) {
                root.right.next = root.next.left;
            }
        }
        
        connect(root.left);
        connect(root.right);
    }
}