JZ86 在二叉树中找到两个节点的最近公共祖先

题目

给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2    
    
    
   ，请找到 o1 和 o2 的最近公共祖先节点    
    
    
    
。 注：本题保证二叉树中每个节点的val值均不相同


     


     


     


   。

方法 BFS     


     


     


     

，非递归方法

思路

算法实现

看到6和7公共祖先有5和3




 




 




 




，但最近的是5
 




 




 




 

。我们只要往上找
   

   

   

  ，找到他们第一个相同的公共祖先节点即可     

     

     

     
， 但怎么找到每个节点的父节点呢 




  




  




  




，我们只需要把每个节点都遍历一遍

  


  


  


 ， 然后顺便记录他们的父节点存储在Map中   

   

   

   

。我们先找到其中的一条路径     
     
     
     ， 比如6→5→3  




   




   




   




，然后在另一个节点往上找


 



 



 



，由于7不在那条路径上                    ， 我们找7的父节点是2   




    




    




    



，2也不在那条路径上


















， 我们接着往上找                   ，2的父节点是5    



     



     



     


，5在那条路径上



















，所以5就是他们的最近公共子节点 

     

     

     

  。

代码

package mid.JZ86在二叉树中找到两个节点的最近公共祖先; import java.util.*; class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; } public class Solution { /** * @param root TreeNode类 * @param o1 int整型 * @param o2 int整型 * @return int整型 */ public int lowestCommonAncestor(TreeNode root, int o1, int o2) { // write code here Queue<TreeNode> queue = new LinkedList<>(); //记录父节点 Map<Integer, Integer> parent = new HashMap<>(); parent.put(root.val, Integer.MIN_VALUE); queue.add(root); //BFS while (!parent.containsKey(o1) || !parent.containsKey(o2)) { TreeNode node = queue.poll(); //左子树 if (node.left != null) { //记录父亲节点 parent.put(node.left.val, node.val); queue.add(node.left); } //左子树 if (node.right != null) { //记录父亲节点 parent.put(node.right.val, node.val); queue.add(node.right); } } //记录祖先节点 Set<Integer> ancestors = new HashSet<>(); //列出o1的所有祖先节点 while (parent.containsKey(o1)) { ancestors.add(o1); o1 = parent.get(o1); } while(!ancestors.contains(o2)) { o2 = parent.get(o2); } return o2; } }