题解 | #在二叉树中找到两个节点的最近公共祖先#

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 int lowestCommonAncestor (TreeNode root, int o1, int o2) { // write code here if (root.val == o1 || root.val == o2){ return root.val; }

    List<TreeNode> toBeTraversed = new ArrayList<>();
    toBeTraversed.add(root);
    Map<Integer, Integer[]> nodeAndParentandLevel = new HashMap<>();
    int level = 1;
    nodeAndParentandLevel.put(root.val, new Integer[]{0, -1});
    while(toBeTraversed.size() > 0){
        TreeNode currentNode = toBeTraversed.get(0);
        toBeTraversed.remove(0);
        if (currentNode.left != null){
            nodeAndParentandLevel.put(currentNode.left.val, 
                                      new Integer[]{level, currentNode.val});
            toBeTraversed.add(currentNode.left);
        }
        if (currentNode.right != null){
            nodeAndParentandLevel.put(currentNode.right.val, 
                                      new Integer[]{level, currentNode.val});
            toBeTraversed.add(currentNode.right);
        }
        level += 1;
    }
    
    Integer[] candidateOne = nodeAndParentandLevel.get(o1);
    Integer[] candidateTwo = nodeAndParentandLevel.get(o2);
    Integer topVal = o2;
    if (candidateOne[0] < candidateTwo[0]){
        Integer[] temp = candidateOne;
        candidateOne = candidateTwo;
        candidateTwo = temp;
        topVal = o1;
    }
    
    while (candidateOne[0] > candidateTwo[0]){
        candidateOne = nodeAndParentandLevel.get(candidateOne[1]);
        if (candidateOne[1] == topVal){
            return topVal;
        }
    }
    
    while (candidateOne[0] >= 1 || candidateTwo[0] >= 1){
        if (candidateOne[1] == candidateTwo[1]){
            return candidateOne[1];
        }
        if (candidateTwo[0] < candidateOne[0]){
            candidateOne = nodeAndParentandLevel.get(candidateOne[1]);
            continue;
        }
        if (candidateOne[0] < candidateTwo[0]){
            candidateTwo = nodeAndParentandLevel.get(candidateTwo[1]);
            continue;
        }
        if (candidateOne[0] == candidateTwo[0]){
            candidateOne = nodeAndParentandLevel.get(candidateOne[1]);
            candidateTwo = nodeAndParentandLevel.get(candidateTwo[1]);
        }
    }
    return root.val;
}

}