Solution to Populating Next Right Pointers in Each Node by LeetCode

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

Question Name: Populating Next Right Pointers in Each Node

# Definition for a binary tree node

# class TreeNode:

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

# self.next = None

class Solution:

# @param root, a tree node

# @return nothing

def connect(self, root):

fatherLayerCurrent = root

sonLayerHead = None

sonLayerCurrent = None

# Travel layer by layer as BFS travesal.

while fatherLayerCurrent != None:

# Travel inside a layer from left to right

while fatherLayerCurrent != None:

# Try to access the left son if there is

if fatherLayerCurrent.left != None:

if sonLayerHead == None:

sonLayerHead = fatherLayerCurrent.left

sonLayerCurrent = sonLayerHead

else:

sonLayerCurrent.next = fatherLayerCurrent.left

sonLayerCurrent = sonLayerCurrent.next

# Try to access the right son if there is

if fatherLayerCurrent.right != None:

if sonLayerHead == None:

sonLayerHead = fatherLayerCurrent.right

sonLayerCurrent = sonLayerHead

else:

sonLayerCurrent.next = fatherLayerCurrent.right

sonLayerCurrent = sonLayerCurrent.next

fatherLayerCurrent = fatherLayerCurrent.next

# Prepare to move down to the next layer.

fatherLayerCurrent = sonLayerHead

sonLayerHead =None

return

The posts in Leetcode’s discussion section is less helpful and misleading sometimes.
I am not even sure if my “ACCEPTED” code is really correct considering the fact the test cases are biased and size is relative small…

class solution{

private:

TreeLinkNode* scan2Right(TreeLinkNode* leftmost)

{

TreeLinkNode *cand = nullptr;

TreeLinkNode* newleftmost = nullptr;

//try to find the first available child

while (nullptr == cand && nullptr != leftmost)

{

cand = leftmost->left;

if (nullptr == cand)

cand = leftmost->right;//is it on the right child?

else

break;//find available child on leftmost->left, break loop before we move leftmost to leftmost->next

leftmost = leftmost->next;//we can safely move to leftmost->next, since even cand is not null, it is the right child of leftmost

}

newleftmost = cand;

while (nullptr != leftmost)

{

if (nullptr != leftmost->left && leftmost->left != cand)

{

cand->next = leftmost->left;

cand = cand->next;

}

else if (nullptr != leftmost->right && leftmost->right != cand)

{

cand->next = leftmost->right;

cand = cand->next;

leftmost = leftmost->next;

}

else

leftmost = leftmost->next;

}

return newleftmost;

}

public:

void connect(TreeLinkNode *root) {

TreeLinkNode *leftmost = root;

while (leftmost)

leftmost = this->scan2Right(leftmost);

}

};

Solution to Populating Next Right Pointers in Each Node by LeetCode

One Reply to “Solution to Populating Next Right Pointers in Each Node by LeetCode”

Leave a Reply Cancel reply