Leetcode 236 二叉树的最近公共祖先

class Solution {
    private HashMap<Integer, Integer> depthMap = new HashMap<>();
    private HashMap<Integer, Integer> parentMap = new HashMap<>();
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 一个HashMap 记录深度, 一个HashMap 记录父节点是什么
        BTS(root,0, null);
        int pVal = p.val;
        int qVal = q.val;
        int pDepth = depthMap.get(pVal);
        int qDepth = depthMap.get(qVal);
        if (pDepth < qDepth){
            for (int i = 0; i < qDepth-pDepth; i++) {
                qVal = parentMap.get(qVal);
            }
        } else {
            for (int i = 0; i < pDepth-qDepth; i++) {
                pVal = parentMap.get(pVal);
            }
        }
        while (pVal != qVal){
            pVal = parentMap.get(pVal);
            qVal = parentMap.get(qVal);
        }
        // 如果这边不许创建新节点, 我甚至打算搞一个 Map 存储节点的引用
        return new TreeNode(pVal);
    }
    private void BTS(TreeNode node, int depth, TreeNode parent){
        if(node == null){
            return;
        }
        if (parent == null){
            parentMap.put(node.val, null);
        } else {
            parentMap.put(node.val, parent.val);
        }
        depthMap.put(node.val, depth);
        if (node.left != null) {
            BTS(node.left, depth+1, node);
        }
        if (node.right != null) {
            BTS(node.right, depth+1, node);
        }

    }
}

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left == null) {
            return right;
        }
        if (right == null) {
            return left;
        }
        return root;
    }
}