Share my O(n) Java Solution without global varible


  • 0
    M

    Each time a TreeNode is generated, the pointer moved one rightwards. In this way, we do not need to use fast and slow to locate the mid node, after left half finishes, the pointer would point exactly at mid node;

    To build a tree, first build left half, after which the pointer will move to mid. Generate root TreeNode from the value of the pointer and move the pointer to the next. Generate right half.

    The recursion invariant is

    • Before: Pointer is always at start of linked list.
    • After left part finishes: Pointer is at middle, ie where the root is.
    • Before Generating right half: Pointer is at start of the right half.
            private class Pointer{
    		ListNode p;
    		public Pointer(ListNode p) {
    			this.p = p;
    		}
    		public void advance() {
    			if (p != null) p = p.next;
    		}
    	}
    	public TreeNode sortedListToBST(ListNode head) {
    		if (head == null) return null;
    		Pointer p = new Pointer(head);
    		int len = 0; 
    		while(head != null) {
    			++len;
    			head = head.next;
    		}
    		return build(p, 0, len - 1);
    	}
    	
    	private TreeNode build(Pointer p, int start, int end) {
    		if (start > end) return null;
    		int mid = (start + end) >>> 1;
    		TreeNode left = build(p, start, mid - 1);
    		TreeNode root = new TreeNode(p.p.val);
    		p.advance();
    		root.left = left;
    		root.right = build(p, mid + 1, end);
    		return root;
    	}
    

Log in to reply
 

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