using DFS to solve this problem


  • 0
    Y

    public class Solution {
    /**
    * @param root: The root of the binary search tree.
    * @param A and B: two nodes in a Binary.
    * @return: Return the least common ancestor(LCA) of the two nodes.
    */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
    //dfs search

         ArrayList<ArrayList<TreeNode>> all=new ArrayList<ArrayList<TreeNode>>();
      
         ArrayList<TreeNode> list=new ArrayList<TreeNode>();
       
         list.add(root);
         
         dfs(all,list,root,A);
         ArrayList<TreeNode> list1=new ArrayList<TreeNode>(all.get(0));
         
         list.clear();
         all.clear();
         
         list.add(root);
         dfs(all,list,root,B);
         ArrayList<TreeNode> list2=new ArrayList<TreeNode>(all.get(0));
         
         HashSet<TreeNode> set=new HashSet<TreeNode>();
         for(TreeNode node:list1)
         {
             set.add(node);
         }
        
         for(int i=list2.size()-1;i>=0;i--)
         {
             if(set.contains(list2.get(i)))
             {
                 return list2.get(i);
             }
         }
         
         return null;
         
    }
    
    public void dfs(ArrayList<ArrayList<TreeNode>> all,ArrayList<TreeNode> list,TreeNode root, TreeNode N)
    {
      
       if(root==N)
       {
           all.add(new ArrayList<TreeNode>(list));
       }
       
       if(root.left!=null)
       {
           list.add(root.left);
           dfs(all,list,root.left,N);
           list.remove(list.size()-1);
       }
       
       
       if(root.right!=null)
       {
         list.add(root.right);
         dfs(all,list,root.right,N);
         list.remove(list.size()-1);
       }
    }
    

    }


  • 0
    Y

    I wonder if there is better way than this to use dfs, I feel the way I wrote is kind of not clever.


Log in to reply
 

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