My bottom-to-up java code using backtracing


  • 0
    F

    searchRoot2NodePath method is to find a path from root to a target tree node. For example,
    a input tree: 1,2,3,#,4,#,#. Then the path of node 4 is 1,2,4, and path of node 3 is 1,3. Then the we pop these 2 path, and find they meet at node 1 , so node 1 is the answer. I use the typical backtracing method to search a path.

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        	List<TreeNode> pathp = new ArrayList<TreeNode>();
        	pathp.add(root);
        	searchRoot2NodePath(root, p, pathp);
        
        	List<TreeNode> pathq = new ArrayList<TreeNode>();
        	pathq.add(root);
        	searchRoot2NodePath(root, q, pathq);
        
        	if (pathp.size() != pathq.size()) {
        		List<TreeNode> longer = pathp.size() > pathq.size() ? pathp : pathq;
        		List<TreeNode> shorter = pathp.size() > pathq.size() ? pathq : pathp;
        		while (longer.size() > shorter.size())
        			longer.remove(longer.size() - 1);
        	}
        	// pathp.size = pathq.size
        	int size = pathp.size();
        	while (size != 0) {
        		if (pathq.get(size - 1) == pathp.get(size - 1))
        			return pathq.get(size - 1);
        		else {
        			pathq.remove(size - 1);
        			pathp.remove(size - 1);
        		}
        	}
        	return null;
        }
        
        public boolean searchRoot2NodePath(TreeNode root, TreeNode target, List<TreeNode> path) {
        	if (root == null)
        		return false;
        	if (root == target)
        		return true;
        	TreeNode l = root.left;
        	path.add(l);
        	boolean status = searchRoot2NodePath(l, target, path);
        	if (status)
        		return true;
        	else
        		path.remove(path.size() - 1);
        
        	TreeNode r = root.right;
        	path.add(r);
        	status = searchRoot2NodePath(r, target, path);
        	if (status)
        		return true;
        	else
        		path.remove(path.size() - 1);
        	return false;
        }

Log in to reply
 

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