My Java solution


  • 0
    L

    recursive solution

    public void connect(TreeLinkNode root) {
        if(root == null)
            return;    
        // if current node's left is null, we ignore it
        if(root.left != null){
            // if left is not null,the left's next is current node's right,whether it is null.
            root.left.next = root.right;
            if(root.next != null)
                root.right.next = root.next.left;
        }
        connect(root.left);
        connect(root.right);
    }
    

    with queue solution

    public void connect(TreeLinkNode root) {
            if(root == null) return;
            List<TreeLinkNode> list = new LinkedList<>();
            list.add(root);
            TreeLinkNode lastNode = null;
            while (!list.isEmpty()){
                int queueSize = list.size();
                for (int i=0;i<queueSize;i++){
                    TreeLinkNode tmpNode = list.remove(0);
                    if(i>0){
                        if(lastNode!=null){
                            lastNode.next = tmpNode;
                        }
                    }
                    lastNode = tmpNode;
                    if(tmpNode!=null){
                        list.add(tmpNode.left);
                        list.add(tmpNode.right);
                    }
    
    
                }
                if(lastNode!=null){
                    lastNode.next = null;
                }
            }
        }
    

Log in to reply
 

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