Leetcode 117) Populating Next Right Pointers in Each Node II

06 Aug 2021 in Algorithms

내 답안

• linkedlist에서 썻던 기법같은 st? 맞네.. 어찌보면 linkedlist와 비슷하니까..
• pre라는 변수에 그 전 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) {
        if(root==null){return root;}
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        Node pre=null;
        while(!q.isEmpty()){
            int size =q.size();
            for(int i =0;i<size;i++){
                Node tmp=q.poll();
                if(pre!=null){
                    pre.next=tmp;
                }
                if(tmp.left!=null){
                    q.add(tmp.left);
                }
                if(tmp.right!=null){
                    q.add(tmp.right);
                }
                pre=tmp;
            }
            pre=null;
        }
        return root;
    }
}

다른 답안

/*
// 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) {
        link(root);
        return root;
    }
    
    private void link(Node root) {
        if(root == null) {
            return;
        }
        if(root.left!=null) {
            Node node = root;
            Node node2 = root.left;
            if(root.right!=null) {
                node2.next = node.right;
                node2 = node2.next;
            }
            node = node.next;
            while(node!=null) {
                if(node.left!=null) {
                    node2.next = node.left;
                    node2 = node.left;
                    if(node.right!=null) {
                        node2.next = node.right;
                        node2 = node2.next;
                    }
                }
                else if(node.right!=null) {
                    node2.next = node.right;
                    node2 = node.right;
                }
                node = node.next;
            }
        }
        else if(root.right!=null) {
            Node node = root;
            Node node2 = root.right;
            while(node.next!=null) {
                node = node.next;
                if(node.left!=null) {
                    node2.next = node.left;
                    node2 = node.left;
                    if(node.right!=null) {
                        node2.next = node.right;
                        node2 = node2.next;
                    }
                }
                else if(node.right!=null) {
                    node2.next = node.right;
                    node2 = node.right;
                }
            }
        }
        Node node3 = root;
        if(root.right==null && root.left == null) {
            node3=node3.next;
                while(node3!=null) {
                    if(node3.left != null || node3.right!=null) {
                        break;
                    }
                    node3=node3.next;
                }
                if(node3==null) {
                    return;
                }
                if(node3.left != null) {
                    Node node = node3;
                    Node node2 = node3.left;
                    if(node3.right!=null) {
                        node2.next = node3.right;
                        node2 = node2.next;
                    }
                    while(node.next!=null) {
                        node = node.next;
                        if(node.left!=null) {
                            node2.next = node.left;
                            node2 = node.left;
                            if(node.right!=null) {
                                node2.next = node.right;
                                node2 = node2.next;
                            }
                        }
                        else if(node.right!=null) {
                            node2.next = node.right;
                            node2 = node.right;
                        }
                    }
                }    
                else if(node3.right!=null) {
                    Node node = node3;
                    Node node2 = node3.right;
                    while(node.next!=null) {
                        node = node.next;
                        if(node.left!=null) {
                            node2.next = node.left;
                            node2 = node.left;
                            if(node.right!=null) {
                                node2.next = node.right;
                                node2 = node2.next;
                            }
                        }
                        else if(node.right!=null) {
                            node2.next = node.right;
                            node2 = node.right;
                        }
                    }
            }
        }
        if(node3.left != null) {
            link(node3.left);
        }    
        else  {
            link(node3.right);
        }
        return;
       
    }
}