A simple solution using recursive in Java. [Space O(1) Accepted]


  • 0
    S

    The solution is recursive, and based on post-order traverse. when case to one node in the tree, if it have both left and right children, make left.next = right, then recursively do the same processing on right and left (right first). After the children node is processed, build the link between left-subtree and right-subtree. Here is a trick, we need check both right and left children, and if left.next already set, just ignore, and visit it children layer.

    public void connect(TreeLinkNode root) {
        if(root == null) return;
        if(root.left != null && root.right != null) root.left.next = root.right;
        connect(root.right);
        connect(root.left);
        connect(root.next, root.right);
        connect(root.next, root.left);
    }
    
    private void connect(TreeLinkNode root, TreeLinkNode prev){
        if(prev == null || root == null) return;
        while(root != null && root.left == null && root.right == null) root = root.next;
        if(root == null) return;
        TreeLinkNode next = root.left != null? root.left : root.right;
        if(prev.next == null)   prev.next = next;
        connect(next, prev.right);
        connect(next, prev.left);
    }

Log in to reply
 

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