Leetcode 116) Populating Next Right Pointers in Each Node

06 Aug 2021 in Algorithms

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

내 답안

/*
// 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) {
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        Node prev=null;
        while(!q.isEmpty()){
            int size= q.size();
            for(int i =0;i<size;i++){
                Node cur = q.poll();
                if(cur==null){
                    return root;
                }
                if(prev!=null){
                    prev.next=cur;
                }
                q.add(cur.left);
                q.add(cur.right);
                prev=cur;
            }
            prev=null;
        }
        return root;
    }
}

다른 답안

class Solution {
    public Node connect(Node root) {
        connectByRecursive(root);
        return root;
    }

    private Node connectByRecursive(Node root){
        if(root == null)
            return null;

        if(root.left != null){
            root.left.next = root.right;
        }

        if(root.right != null){
            if(root.next != null){
                root.right.next = root.next.left;
            }else{
                root.right.next = null;
            }
        }

        connectByRecursive(root.left);
        connectByRecursive(root.right);
        return root;
    }

}