Java - build the paths in stacks from nodes to root with DFS, return the first crossing point on paths


  • 7
    J
    public class Solution {
    
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    	Stack<TreeNode> pStack = new Stack<TreeNode>();
    	Stack<TreeNode> qStack = new Stack<TreeNode>();
    	TreeNode target = null;
    	if (findPath(root, p, pStack) && findPath(root, q, qStack)) {
     		while (!pStack.isEmpty()) {
     			TreeNode pNode = pStack.pop();
    			if (qStack.contains(pNode))
    				target = pNode;
    		}
    	} 
    	return target;
    }
    
    private boolean findPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
    	if (root == null)
    		return false;
    	if (root == node) {
    		stack.push(root);
    		return true;
    	} else {
    		if (findPath(root.left, node, stack) ||  findPath(root.right, node, stack)) {
    		    stack.push(root);
    			return true;
    		}
    	}
    	return false;
    }
    

    }


  • 0
    O

    For this solution you need do DFS on the tree twice, also stack.contains is O(n) complexity. So your solution is acturally 2n + k^2. Why not just return 2 stack/deque from one DFS and search the last same node from the head?


  • 0
    G

    Similar solution with some trival improvements.

    1. call findPath function just once.

    2. search the target Treenode from the beginning of two lists, because the time complexity of contains functions is O(n).

    3. use label as a flag variable, which indicates when we can exit early.

       public class LowestCommonAncestorBinaryTree {
         LinkedList<TreeNode> stack = new LinkedList<>();
         List<TreeNode> path1 = new ArrayList<>();
         List<TreeNode> path2 = new ArrayList<>();
         int label = 0;
      
         public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
         findPath(root, p, q);
       
         int index = 0;
         TreeNode result = null;
         while(index < Math.min(path1.size(), path2.size())) {
         if(path1.get(index) == path2.get(index)) {
           result = path1.get(index);
         } else {
           break;
         }
         index++;
         }
       
         return result;
         }
      
       public void findPath(TreeNode root, TreeNode p, TreeNode q) {
         if(label == 2) {
           return;
         }
         stack.addLast(root);
       
         if(root == p) {
           label++;
           path1.addAll(stack);
         }
         if(root == q) {
           label++;
           path2.addAll(stack);
         }
       
         if(root.left != null) {
           findPath(root.left, p, q);
         }
         if(root.right != null) {
           findPath(root.right, p, q);
         }
       
         stack.removeLast();
         }
       }

Log in to reply
 

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