Java Solution, Easy to Understand, O(n) time ,Iterative solution


  • 0
    G

    Used a queue for level order traversal .
    At each level start from right end and keep a tail pointer.
    So for rightmost node next pointer is null.
    After that just make the current node as the tail pointer

    Here is the code

    public void connect(TreeLinkNode root) {
            if(root==null)return;
            Queue<TreeLinkNode>queue = new LinkedList<TreeLinkNode>();
            queue.add(root);
            while(!queue.isEmpty()){
                LinkedList<TreeLinkNode>level = new LinkedList<TreeLinkNode>();
                int size = queue.size();
                TreeLinkNode tailEnd = null;
                TreeLinkNode current = null;
                for(int i=size-1;i>=0;i--){
                    current = queue.poll();
                    current.next = tailEnd;
                    tailEnd = current;   
                    if(current.right!=null)queue.add(current.right);
                    if(current.left!=null)queue.add(current.left);
                }
            }
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.