My solution ,may be not so good,but clear


  • 5
    L

    First, we use a map to save the node and its parent for all nodes.
    This saves all the path from leaves to the root.
    Second, from Node p ,we climb to the root to form a Route of Nodes
    Finally , let the q goes up until it touches the route.

    public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        HashMap<TreeNode,TreeNode> m = new HashMap<TreeNode,TreeNode>();
        // bfs walking tree
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while(queue.peek()!=null){
            TreeNode t = queue.poll();
            if(t.left!=null){
                m.put(t.left,t);
                queue.offer(t.left);
            }
            if(t.right!=null){
                m.put(t.right,t);
                queue.offer(t.right);
            }
        }
        // build route
        Set<TreeNode> l = new HashSet<TreeNode>();
        TreeNode pp = p;
        while(pp!=root){
            l.add(pp);
            pp = m.get(pp);
        }
        l.add(root);
        TreeNode qq = q;
        while(!l.contains(qq)){
            qq = m.get(qq);
        }
        return qq;
    }
    

    }


  • 0
    L

    I thought of this too. :) The good part is the time complexity is only O(n) and the bad part is the space complexity is also O(n). So later I reduced the space complexity to O(logn) while keep the O(n) time cost. If you are interested in it, have a try :)


  • 0
    Y

    @liji94188, could you share your idea :-) Thanks


  • 0
    L

    just build up the path from root to p and q respectively, and go through the two paths, the node before first uncommon node in two paths is the lowest common ancestor. And we only need O(logn) space to build up the path. :)


  • 0
    Y

    Thanks for reply! Could you elaborate how to build path from room to p and q with O(logN) space? I am kind of stuck...


  • 0
    L

    key idea is DFS search. if we didn't find p when reach a leaf node, we need to back track and delete all the nodes that proved to be not on the path. maybe some other elegant way to build up path exist :)


  • 0
    L

    List<TreeNode> res = new LinkedList<TreeNode>();
    public void findPath(TreeNode root, TreeNode p, int[] found){
    if(root==null) return;
    else if(root==p){
    found[0] = 1;
    res.add(root);
    return;
    }
    else{
    res.add(root);
    findPath(root.left,p,found);
    if(found[0]==1) return;
    else{
    while(res.get(res.size()-1)!=root) res.remove(res.size()-1);
    findPath(root.right,p,found);
    if(found[0]==1) return;
    else{
    while(res.get(res.size()-1)!=root) res.remove(res.size()-1);
    res.remove(res.size()-1);
    return;
    }
    }
    }
    }


  • 0
    Y

    Thank you! Let me study this.


  • 1
    L

    Just notice the code for building up a path to a given TreeNode is not easy to read, so I paste it here.

    It uses only O(logN) memory to store the current path.

    public void findPath(TreeNode root, TreeNode p, int[] found, List<TreeNode> res){
        	if(root==null) return;
        	else if(root==p){
        		found[0] = 1;
        		res.add(root);
                return;
        	}
        	else{
        		res.add(root);
        		findPath(root.left,p,found,res);
        		if(found[0]==1) return;
        		else{
        			while(res.get(res.size()-1)!=root) res.remove(res.size()-1);
        			findPath(root.right,p,found,res);
        		}
        	}
        } 

  • 0
    H

    Really ez to understand, thank you!


  • 0
    L

    @hwmiku . I thought of this on the way to work two years ago. There was a recursive
    solution when I read a book


Log in to reply
 

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