[LeetCode] 116. Populating Next Right Pointers in Each Node - 넓이우선탐색(BFS) + 깊이우선탐색(DFS) + 아이디어(Idea) JAVA

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

코드설명

넓이우선탐색(BFS) + 깊이우선탐색(DFS) 활용합니다.

 

BFS를 사용하는 경우는, 완전이진트리가 아니어도 가능합니다.

DFS의 경우에는 완전이진트리일 경우에만 가능합니다.

 

이 문제에서는 완전이진트리일 경우이기에, DFS를 사용하는것이 공간복잡도가 O(1)이기에, DFS 사용하는 것이 더 좋습니다. 만약, 완전이진트리라는 조건이 없을경우에는 BFS를 사용해야겠지요.

코드

BFS를 활용한 코드입니다. 공간복잡도 O(N) 입니다.

/*
// 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;
    }
};
*/

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

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

        while(!q.isEmpty()){
            int size = q.size();
            Node prev = null;
            for(int i=0; i<size; i++){
                Node node = q.poll();

                if(prev != null){
                    prev.next = node;
                }
                prev = node;
                
                if(node.left != null) q.add(node.left);
                if(node.right != null) q.add(node.right);
            }
        }   

        return root;    
    }
}

 

DFS를 활용한 코드입니다. (공간복잡도가 O(1)) 입니다.

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

        Node levelStart = root;

        while (levelStart.left != null) { // 완전 이진 트리이므로 왼쪽이 null이면 더 내려갈 수 없음
            Node curr = levelStart;

            while (curr != null) {
                curr.left.next = curr.right;
                if (curr.next != null) {
                    curr.right.next = curr.next.left;
                }
                curr = curr.next;
            }
            levelStart = levelStart.left; // 다음 레벨로 이동
        }
        return root;
    }
}