find the path between nodes in binary tree

By | November 30, 2014
Share the joy
  •  
  •  
  •  
  •  
  •  
  •  

I made this code, it is because I saw there is a problem in geeksforgeeks: link
But it only gets the distance of 2 nodes. I’m thinking how to get the path of the 2 nodes. The idea is inspired by Pavel Fusu’s code. link

The process is below:
1. Find the lca node. link
2. Find the path1 and path2 from the lca to the designated nodes.
3. Merge path1 and path2

  1. public class LCA {
  2.     public static void main(String[] args) {
  3.         Tree tree = Tree.getTree();
  4.         ArrayList<Integer> path = findNodesPath(tree, 9, 18);
  5.         printPath(path);
  6.     }
  7.     /*
  8.      * Find the LCA of node1 and node2
  9.      */
  10.     public static Tree findLca(Tree tree, MyInteger lcaNum, int node1, int node2){
  11.         if(tree==null){
  12.             return null;
  13.         }
  14.         MyInteger lLca = new MyInteger(0);
  15.         Tree ltree = findLca(tree.left, lLca, node1, node2);
  16.         if(lLca.i==2){
  17.             lcaNum.i=2;
  18.             return ltree;
  19.         }
  20.         MyInteger rLca = new MyInteger(0);
  21.         Tree rtree = findLca(tree.right, rLca, node1, node2);
  22.         if(rLca.i==2){
  23.             lcaNum.i=2;
  24.             return rtree;
  25.         }
  26.         int selfLca = 0;
  27.         if(node1==tree.value||node2==tree.value){
  28.             selfLca = 1;
  29.         }
  30.         lcaNum.i = lLca.i + rLca.i + selfLca;
  31.         return tree;
  32.     }
  33.     /*
  34.      * Find the path of node under root.
  35.      */
  36.     public static boolean findPath(Tree root, int node, ArrayList<Integer> path){
  37.         if(root==null){
  38.             return false;
  39.         }
  40.         boolean lHas = findPath(root.left, node, path);
  41.         if(lHas){
  42.             path.add(root.value);
  43.             return true;
  44.         }
  45.         boolean rHas = findPath(root.right, node, path);
  46.         if(rHas){
  47.             path.add(root.value);
  48.             return true;
  49.         }
  50.         if(root.value==node){
  51.             path.add(root.value);
  52.             return true;
  53.         }
  54.         return false;
  55.     }
  56.     /*
  57.      * Find the path of node1(or node2) under root.
  58.      */
  59.     public static boolean findPath(Tree root, int node1, int node2, ArrayList<Integer> path){
  60.         if(root==null){
  61.             return false;
  62.         }
  63.         if(findPath(root.left, node1, node2, path)){
  64.             path.add(root.value);
  65.             return true;
  66.         }
  67.         if(findPath(root.right, node1, node2, path)){
  68.             path.add(root.value);
  69.             return true;
  70.         }
  71.         if(root.value==node1||root.value==node2){
  72.             path.add(root.value);
  73.             return true;
  74.         }
  75.         return false;
  76.     }
  77.     /*
  78.      * Find the path between node1 and node2
  79.      */
  80.     public static ArrayList<Integer> findNodesPath(Tree tree, int node1, int node2){
  81.         MyInteger lcaNum = new MyInteger(0);
  82.         Tree lca = findLca(tree, lcaNum, node1, node2);
  83.         if(lcaNum.i<2){
  84.             return null;
  85.         }
  86.         ArrayList<Integer> path1 = new ArrayList<Integer>();
  87.         ArrayList<Integer> path2 = new ArrayList<Integer>();
  88.         findPath(lca.left, node1, node2, path1);
  89.         findPath(lca.right, node1, node2, path2);
  90.         path1.add(lca.value);
  91.         while(!path2.isEmpty()){
  92.             path1.add(path2.remove(path2.size()-1));
  93.         }
  94.         return path1;
  95.     }
  96.     public static void printPath(ArrayList<Integer> path){
  97.         if(path==null){
  98.             return;
  99.         }
  100.         Iterator<Integer> itr = path.iterator();
  101.         while(itr.hasNext()){
  102.             System.out.print(itr.next()+” “);
  103.         }
  104.         System.out.println();
  105.     }
  106. }
  107. public class MyInteger{
  108.     public int i = 0;
  109.     public MyInteger(int i){
  110.         this.i = i;
  111.     }
  112.     public String toString(){
  113.         return String.valueOf(i);
  114.     }
  115. }