Skip to content

117. Populating Next Right Pointers in Each Node II

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

js
/**
 * // Definition for a Node.
 * function Node(val,left,right,next) {
 *    this.val = val;
 *    this.left = left;
 *    this.right = right;
 *    this.next = next;
 * };
 */
/**
 * @param {Node} root
 * @return {Node}
 */
function connect(root) {
    let parent = null
    let leftMost = root
    let node = null

    while (leftMost) {
        parent = leftMost
        leftMost = null
        node = null

        while (parent) {
            if (!leftMost) {
                leftMost = parent.left
            }
            if (!leftMost) {
                leftMost = parent.right
            }

            if (parent.left) {
                if (node) {
                    node.next = parent.left
                }
                node = parent.left
            }
            if (parent.right) {
                if (node) {
                    node.next = parent.right
                }
                node = parent.right
            }

            parent = parent.next
        }
    }

    return root
}
js
/**
 * // Definition for a Node.
 * function Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 */
/**
 * @param {Node} root
 * @return {Node}
 */
var connect = function(root) {
    if (!root) {
        return null
    }

    let current = [root]
    let next = []

    while (current.length > 0) {
        for (let i = 0; i < current.length; i++) {
            if (i < current.length - 1) {
                current[i].next = current[i + 1]
            }
            if (current[i].left) {
                next.push(current[i].left)
            }
            if (current[i].right) {
                next.push(current[i].right)
            }
        }
        current = next
        next = []
    }

    return root
};
py
"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, left, right, next):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""


class Solution(object):

    def connect(self, root):
        """
        :type root: Node
        :rtype: Node
        """
        parent = None
        leftMost = root
        node = None

        while leftMost:
            parent = leftMost
            leftMost = None
            node = None

            while parent:
                if not leftMost:
                    leftMost = parent.left
                if not leftMost:
                    leftMost = parent.right

                if parent.left:
                    if node:
                        node.next = parent.left
                    node = parent.left
                if parent.right:
                    if node:
                        node.next = parent.right
                    node = parent.right

                parent = parent.next

        return root
py
"""
# Definition for a Node.
class Node(object):
    def __init__(self, val=0, left=None, right=None, next=None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""


class Solution(object):

    def connect(self, root):
        """
        :type root: Node
        :rtype: Node
        """
        if not root:
            return None

        current, nextRow = [root], []

        while current:
            for i, node in enumerate(current):
                if i < len(current) - 1:
                    node.next = current[i + 1]
                if node.left is not None:
                    nextRow.append(node.left)
                if node.right is not None:
                    nextRow.append(node.right)
            current = nextRow
            nextRow = []

        return root
go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 *     Next *TreeNode
 * }
 */
func connect(root *TreeNode) *TreeNode {
	var parent *TreeNode
	var leftMost = root
	var node *TreeNode

	for leftMost != nil {
		parent = leftMost
		leftMost = nil
		node = nil

		for parent != nil {
			if leftMost != nil {
				leftMost = parent.Left
			}
			if leftMost != nil {
				leftMost = parent.Right
			}
			if parent.Left != nil {
				if node != nil {
					node.Next = parent.Left
				}
				node = parent.Left
			}
			if parent.Right != nil {
				if node != nil {
					node.Next = parent.Right
				}
				node = parent.Right
			}
			parent = parent.Next
		}
	}

	return root
}