Super short Java recursion solution with O(1) space and another iterative BFS O(n) time and O(1) space.


  • 3
    L

    Code is short and easy to understand, the merge part is just like a DFS in two trees simultaneously, the order of the four recursions matters.

    Then the pain is the time complexity. It's slow but just enough to get AC.

    public class Solution {
        public void connect(TreeLinkNode root) {
        	if(root==null) return; 
        	connect(root.left);
        	connect(root.right);
        	merge(root.left,1,root.right,new int[1]);
        }
        
        public void merge(TreeLinkNode rootL, int currDepth, TreeLinkNode rootR, int[] visitedDepth){
        	if(rootL==null || rootR==null) return;
        	if(currDepth> visitedDepth[0]) {
        		rootL.next = rootR;
        		visitedDepth[0]++;
        	}
        	merge(rootL.right,currDepth+1,rootR.left,visitedDepth);
        	merge(rootL.right,currDepth+1,rootR.right,visitedDepth);
        	merge(rootL.left,currDepth+1,rootR.left,visitedDepth);
        	merge(rootL.left,currDepth+1,rootR.right,visitedDepth);
        }
    }
    

    Here is iterative BFS solution with O(n) time complexity and O(1) space.

    Explanation for 2nd solution: It's a BFS traversal inspired by aileengw. The curr pointer is the current level traveler and head is the left most element at next level and the tail is the right most element at next level till now. We move curr pointer at current level and populate the the next-link at its children level. (Here the gist is we can move curr to its next because this relationship was already populated in the previous round).

    public class Solution {
        public void connect(TreeLinkNode root) {
        	TreeLinkNode curr = root;
        	TreeLinkNode head = null, tail = null;
        	while(curr!=null) {
        	    if(curr.left!=null) {
        	        if(tail!=null) {
        	            tail.next = curr.left;
        	            tail = tail.next;
        	        }
        	        else {
        	            head = curr.left;
        	            tail = head;
        	        }
        	    }
        	    if(curr.right!=null) {
        	        if(tail!=null) {
        	            tail.next = curr.right;
        	            tail = tail.next;
        	        }
        	        else {
        	            head = curr.right;
        	            tail = head;
        	        }
        	    }
        	    if(curr.next!=null) curr = curr.next;
        	    else {
        	        curr = head;
        	        head = null;
        	        tail = null;
        	    }
        	}
        }
    }
    

  • 0
    L

    Explanation for 2nd solution: It's a BFS traversal inspired by aileengw. The curr pointer is the current level traveler and head is the left most element at next level and the tail is the right most element at next level till now. We move curr pointer at current level and populate the the next-link at its children level. (Here the gist is we can move curr to its next because this relationship was already populated in the previous round).


Log in to reply
 

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