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

描述

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

数据范围：树上节点数满足 1 \le n \le 10^5 \1≤n≤105  , 节点值val满足区间 [0,n)

要求：时间复杂度 O(n)O(n)

注：本题保证二叉树中每个节点的val值均不相同。

如当输入{3,5,1,6,2,0,8,#,#,7,4},5,1时，二叉树{3,5,1,6,2,0,8,#,#,7,4}如下图所示：

转存失败重新上传取消

所以节点值为5和节点值为1的节点的最近公共祖先节点的节点值为3，所以对应的输出为3。

节点本身可以视为自己的祖先

示例1

输入：

{3,5,1,6,2,0,8,#,#,7,4},5,1

复制返回值：

3

复制

示例2

输入：

{3,5,1,6,2,0,8,#,#,7,4},2,7

复制返回值：

2

使用dfs加hashmap

思路：

1. dfs首先遍历所有的路径（这是一点看法，dfs不仅仅是遍历节点也是遍历路径）

2. 记录两个需要的节点的路径，但是（一开始的想法是记录两个链表，这样的话会导致找到第一个公共祖先的时候，消耗时间），所以一个使用hashmap，一个使用链表，就很好，把搜索公共节点的时间压缩到o(1)。

import java.util.*;
 
/*
 * public 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 void dfs (TreeNode root, int o1, int o2) {
        // write code here
        if(root==null)return ;
        list.addLast(root.val);
        if(root.val==o1){
            for(Integer x:list){
                hashmap1.put(x,1);
            }
        }
        if(root.val==o2){
            res=(LinkedList<Integer>)list.clone();
        }
        
        dfs(root.left,o1,o2);
        dfs(root.right,o1,o2);
        list.removeLast();
    }
    HashMap<Integer,Integer> hashmap1=new HashMap<Integer,Integer>();//必须用Integer
//     HashMap<Integer,Integer> hashmap2=new HashMap<Integer,Integer>();
    LinkedList<Integer> list=new LinkedList<>();
    LinkedList<Integer> res=new LinkedList<>();
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        dfs(root,o1,o2);
        int ans=0x7fffffff;
       
        for(int x:res){
            System.out.println(x);
            if(hashmap1.containsKey(x)){
                ans=x;
            }
        }
        return ans;
    }
}

这种没有父节点 ，需要父节点的题目，可以使用hashmap存储父节点

import java.util.*;
 
/*
 * public 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整型
     */
    int inf=0x7fffffff;
    HashMap<Integer,Integer> hashmap=new HashMap<Integer,Integer>();
    public void dfs(TreeNode root,int  parent){
        hashmap.put(root.val,parent);
        if(root.left!=null)
            dfs(root.left,root.val);
        if(root.right!=null)
            dfs(root.right,root.val);
    }
   
    HashSet<Integer> hashset=new HashSet<Integer>();
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
         dfs(root,inf);
      //  System.out.println("1");
        hashset.add((o1));
        while(hashmap.get(o1)!=inf){
            hashset.add(hashmap.get(o1));
            o1=hashmap.get(o1);
        }
       //   System.out.println("2");
        while(!hashset.contains(o2)){
            o2=hashmap.get(o2);
        }
        // System.out.println("3");
        
        return o2;
    }
}

思路：

1. 使用hashmap保存所有的父亲节点

2. 找到根节点开始的路径，把两台路径之中的共同父母找到（一个使用hashset一个遍历）

public int lowestCommonAncestor(TreeNode root, int o1, int o2) {
    return helper(root, o1, o2).val;
}
 
public TreeNode helper(TreeNode root, int o1, int o2) {
    if (root == null || root.val == o1 || root.val == o2)
        return root;
    TreeNode left = helper(root.left, o1, o2);
    TreeNode right = helper(root.right, o1, o2);
    //如果left为空，说明这两个节点在root结点的右子树上，我们只需要返回右子树查找的结果即可
    if (left == null)
        return right;
    //同上
    if (right == null)
        return left;
    //如果left和right都不为空，说明这两个节点一个在root的左子树上一个在root的右子树上，
    //我们只需要返回cur结点即可。
    return root;
}

思路:使用递归函数

1. 设计的时候有两点一个是递归条件，一个是终结时候的返回值

2. 假设这个函数是取得该子树下的

        a。如果o1,o2都存在，得到公共祖先

        b。只存在一个，得到一个

        c。都不存在，返回null

3. 递归条件是使用这个函数，实现这个函数的功能。（这一点其实就是设计这个函数功能的依据）

          a 首先看根节点是否是o1,o2，如果是则返回

          b  根节点不是的情况下

                1 递归左节点和右节点的结果不为空，说明左节点一个，右节点一个，返回root

                2递归左节点和右节点的结果一个为空，都在左子树，或者都在右子树，返回不为空的那个。

                3递归左节点和右节点的结果都为空，返回空

   如果这样的话，那么看他是否能够实现刚刚说的三个功能。结果是可以实现。

！！！我认为在设计该函数的时候，先去实现假设两个都在子树里面的情况，然后再去补充实现只有一个或者一个都没有的情况。

4. 最后考虑临界条件，最终我们会递归到叶子节点或者是null节点，电子管这个时候，我们看null返回null，叶子节点如果是目标节点，直接返回，这个是满足刚刚的假设条件的。