思路：使用map存儲每個節點的父節點，則兩個節點的最近公共祖先，即二者的最近父節點

1、中序遍歷二叉樹（當前節點的下一個節點）
2、記錄每個節點的父節點
3、列出p的族譜、q的族譜
4、尋找二者最近的祖先

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode n1, TreeNode n2) {if (n1.val == root.val || n2.val == root.val) {return root;}// 1.尋找所所有節點的父節點Map<TreeNode, TreeNode> map = new HashMap<>();findParent(map, root);// 2.n1的家譜（包括自己）List<TreeNode> n1ParentList = getPeople(map, n1);// 3.n2的家譜List<TreeNode> n2ParentList = getPeople(map, n2);// 4.n1和n2的公共長輩的第一個長輩n1ParentList.retainAll(n2ParentList);return n1ParentList.get(0);}private void findParent(Map<TreeNode, TreeNode> map, TreeNode root) {map.put(root, null);TreeNode temp = root;// 1.最左子節點while (temp.left != null) {map.put(temp.left, temp);temp = temp.left;}// 2.下一個節點TreeNode curNode = temp;while (true) {TreeNode nextNode = next(map, curNode);if (nextNode == null) {return;}curNode = nextNode;}}private TreeNode next(Map<TreeNode, TreeNode> map, TreeNode curNode) {if (curNode.right != null) {TreeNode next = curNode.right;map.put(next, curNode);while (next.left != null) {map.put(next.left, next);next = next.left;}return next;} else {TreeNode parent = map.get(curNode);while (true) {if (parent == null) {return null;} else if (parent.left != null && Objects.equals(parent.left.val, curNode.val)) {return parent;} else {curNode = parent;parent = map.get(curNode);}}}}private List<TreeNode> getPeople(Map<TreeNode, TreeNode> map, TreeNode node) {List<TreeNode> list = new ArrayList<>();while (node != null) {list.add(node);TreeNode parent = map.get(node);node = parent;}return list;}
}