Shortest Path between Two Nodes

Given two nodes that are in a binary tree (this is guaranteed) find the shortest traversal path between them.
Solution1:
先用LCA找到ancestor，然后打印path。

public class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode(int x) { val = x; }
 } 
 
 public static List shortestPath(TreeNode root, TreeNode A, TreeNode B) {
  if(root == null) {
   return null;
  }
  
  Stack pathL = new Stack();
  Stack pathR = new Stack();
  
  TreeNode ancestor = lowestCommonAncestor(root, A, B);
  TreeNode node = ancestor;
  
  helper(node.left, A, B, pathL);
  helper(node.right, A, B, pathR);
  
  pathL.push(node);
  while(!pathR.isEmpty()) {
   pathL.push(pathR.pop());
  }
  
  for(TreeNode t: pathL) {
   System.out.print(t.val + " ");
  }

  return pathL;
 }
 
 public static boolean helper(TreeNode root, TreeNode A, TreeNode B, Stack path) {
  if(root == null) {
   return false;
  }

  if(root.val == A.val || root.val == B.val) {
   path.push(root);
   return true;
  }
  
  if (helper(root.left, A, B, path) ||  helper(root.right, A, B, path)) {  //DFS
      path.push(root);
      return true;
  }
  return false;
  
 }
 
 public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
  
  if(root == null) {
            return null;
        }
  
        if(root == A || root == B) {
         return root;
        }
        
         
        TreeNode left = lowestCommonAncestor(root.left, A, B);
        TreeNode right = lowestCommonAncestor(root.right, A, B);
        
        if(left != null && right != null) {  // if A and B are on both sides
            return root;
        }
         
        if(left != null) {  // either one of A,B is on one side OR A,B is not in L&R subtrees
            return left;
        }else {
            return right;
        }
    }

From Han Chen

Solution2:

package leetcode;

import java.util.*;
import java.lang.*;
import java.io.*;
  
class TreeNode {
      public int val;
      public TreeNode left, right;
      public TreeNode(int val) {
          this.val = val;
          this.left = this.right = null;
      }
  }
 
class Shibai
{
 public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
  if (A == root) {
 
   return root;
  }
 
  if (B == root) {
   return root;
  }
 
  if (root == null) return root;
 
  TreeNode left = lowestCommonAncestor(root.left,A,B);
        TreeNode right = lowestCommonAncestor(root.right,A,B);
 
        if (left == null && right == null) return null;
 
        if (left != null && right != null) {
 
            return root;
        }
 
        if (left != null) {
 
         return left;
        }else {
 
         return right;
        }
 
 }
 
 public static TreeNode p(TreeNode r, TreeNode t,List arr) {
  if (r == t || r == null) return r;
  TreeNode left = p(r.left,t,arr);
  TreeNode right = p(r.right,t,arr);
  if (left != null || right != null) {
   arr.add(r);
  }
 
  return left != null? left:right;
 }
 
 
 public static void main (String[] args) throws java.lang.Exception
 {
  // your code goes here
  TreeNode root1 = new TreeNode(1);
  TreeNode root2 = new TreeNode(2);
  TreeNode root3 = new TreeNode(3);
  TreeNode root4 = new TreeNode(4);
  TreeNode root5 = new TreeNode(5);
  TreeNode root6 = new TreeNode(6);
  TreeNode root7 = new TreeNode(7);
  TreeNode root8 = new TreeNode(8);
 
  root1.left = root2;
  root1.right = root3;
  root2.left = root4;
  root2.right = root5;
  root3.left = root6;
  root3.right = root7;
  root6.left = root8;
 
  List arr1 = new ArrayList();
  List arr2 = new ArrayList();
  TreeNode A = root4;
  TreeNode B = root8;
 
  TreeNode lca = lowestCommonAncestor(root1,A,B);
 
  //arr1.addAll(arr2);
  arr1.add(A);
  TreeNode t1 = p(lca,A,arr1);
 
  TreeNode t2 = p(lca,B,arr2);
  
  Collections.reverse(arr2);
  arr2.add(B);
  arr2.remove(0);

  for (int i = 0; i < arr1.size(); i++) {
   System.out.println(arr1.get(i).val);
  }
  System.out.println("-------");
  for (int i = 0; i < arr2.size(); i++) {
   System.out.println(arr2.get(i).val);
  }
 }
}

From Shibai