Java constant extra space, O(n) solution


  • 0
    O
    /*
        Time complexity: O(n), Space complexity: constant extra space
         */
        public static void connect2(TreeLinkNode root){
            if(root == null){
                return;
            }
            TreeLinkNode pre = null;
            TreeLinkNode current = root;
            TreeLinkNode currentLevelHead = root;
            TreeLinkNode nextLevelHead = null;
    
            while(currentLevelHead != null) {
                current = currentLevelHead;
                while (current != null) { //linking current level nodes while constructing next level
                    //left child
                    if (current.left != null) {
                        if (pre != null) {
                            pre.next = current.left;
                        } else {
                            nextLevelHead = current.left;
                        }
                        pre = current.left;
                    }
                    //right child
                    if (current.right != null) {
                        if (pre != null) {
                            pre.next = current.right;
                        } else {
                            nextLevelHead = current.right;
                        }
                        pre = current.right;
                    }
                    current = current.next;
                }
                currentLevelHead = nextLevelHead;
                pre = null;
                nextLevelHead = null;
            }
        }
    

Log in to reply
 

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