力扣 | 236. 二叉树的最近公共祖先

用HashMap维护好子节点和父节点的关系

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode() {
    }

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Problem_236_LowestCommonAnstor {
    public TreeNode lowestCommonAnster(TreeNode root,TreeNode p,TreeNode q){

        Map<Integer,TreeNode> parent = new HashMap<>();
        dfs(root,parent);
        Set<Integer> visited = new HashSet<>();
        while (p != null){
            visited.add(p.val);
            p = parent.get(p.val);
        }
        while (q != null){
            if(visited.contains(q.val))return q;
            q = parent.get(q.val);
        }
        //如果有一个为null的话 其公共祖先为 null
        return null;
    }
    public void dfs(TreeNode root,Map<Integer,TreeNode> parent){
        if(root == null)return;
        if(root.left != null)parent.put(root.left.val, root);
        if(root.right != null)parent.put(root.right.val,root);
        dfs(root.left,parent);
        dfs(root.right,parent);
    }

}