Morris Traversal solving it using O(1) extra space, O(n) time.


  • 0
    O

    The algorithm used Morris traversal, and the reduction from LCA to RMQ. For the reduction, see Reduction from LCA to RMQ (Topcoder's tutorial for RMQ and LCA)

    The actual running time is longer than most recursive solutions. I posted it as it uses O(1) extra space. So some people might be interested in it.
    The idea is not hard to understand if you understand Morris traversal. Here, the traversal is the in-order traversal of binary tree. Wish it helpful.

    
    
    	private TreeNode w;
    	private boolean gathering;
    	private int minLevel;
    
    	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    		w = null;
    		gathering = false;
    		minLevel = -1;
    
    		TreeNode u = root;
    		int level = 0;
    
    		while (u != null) {
    			if (u.left == null) {
    				if (visit(u, level, p, q))
    					break;
    				else {
    					u = u.right;
    					level++;
    				}
    			} else {
    				int delta = 1;
    				TreeNode v = u.left;
    
    				while (v.right != null && v.right != u) {
    					v = v.right;
    					delta++;
    				}
    				if (v.right == null) {
    					v.right = u;
    					u = u.left;
    					level++;
    				} else {
    					v.right = null;
    					level -= delta + 1;
    					if (visit(u, level, p, q))
    						break;
    					else {
    						u = u.right;
    						level++;
    					}
    				}
    			}
    		}
    		return w;
    	}
    
    	private void restoreTree(TreeNode u) {
    		u = u.right;
    		while (u != null) {
    			if (u.left == null)
    				u = u.right;
    			else {
    				TreeNode v = u.left;
    				while (v.right != null && v.right != u)
    					v = v.right;
    				if (v.right == u)
    					v.right = null;
    				u = u.right;
    			}
    		}
    	}
    
    	private boolean visit(TreeNode u, int level, TreeNode p, TreeNode q) {
    		if (u == p || u == q) {
    			if (!gathering) {
    				gathering = true;
    				w = u;
    				minLevel = level;
    			} else {
    				if (level < minLevel) {
    					w = u;
    					minLevel = level;
    				}
    				restoreTree(u);
    				return true;
    			}
    		} else {
    			if (gathering) {
    				if (level < minLevel) {
    					w = u;
    					minLevel = level;
    				}
    			}
    		}
    		return false;
    	}
    

Log in to reply
 

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