[Binary Tree General][Medium] 117. Populating Next Right Pointers in Each Node II

Q. 주어진 트리에서 next 포인터를 위 예시와 같이 지정하도록 하라. 

 

 

Solution. 

 BFS 를 알고 있다면 간단한 문제. 

 depth 별로 node를 추린 후에 뒤에서 부터 next 포인터를 정리한다.

 

 코드 

public Node Connect(Node root) 
{
    if(root == null)
        return root;

    Queue<Node> qBuff = new Queue<Node>();
    qBuff.Enqueue(root);
    while(qBuff.Count > 0)
    {
        int cnt = qBuff.Count;
        List<Node> listNodes = new List<Node>();
        for(int q = 0; q < cnt; ++q)
        {   
            Node node = qBuff.Dequeue();
            listNodes.Add(node);

            if(node.left != null)   qBuff.Enqueue(node.left);
            if(node.right != null)  qBuff.Enqueue(node.right);
        }
        Node right = null;
        for(int q = 0; q < listNodes.Count; ++q)
        {
            int idx = listNodes.Count-1-q;
            listNodes[idx].next = right;
            right = listNodes[idx];
        }
    }
    return root;
}

 

 

 

결과