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

package org.example; import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Set; class Solution { /** * 父结点哈希表 key结点 value结点的父结点 */ private final MapTreeNode, TreeNode parent new HashMap(); public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { // 构建缓存 buildCache(root); TreeNode pointer null; // 记录 p 结点回溯过程中经过的所有结点 SetTreeNode path new HashSet(); // 开始回溯 p 结点 pointer p; while (pointer ! null) { // 更新 path path.add(pointer); // 更新 pointer 为当前指向的结点的父结点 pointer parent.get(pointer); } // 开始回溯 q 结点 pointer q; while (pointer ! null) { // 检查 path 中是否包含该结点 if (path.contains(pointer)) { return pointer; } else { // 更新 pointer 为当前指向的结点的父结点 pointer parent.get(pointer); } } return null; } /** * 构建缓存 * * param root 根结点 */ private void buildCache(TreeNode root) { if (root null) { return; } // 更新缓存 // 记录左孩子的父结点 if (root.left ! null) { parent.put(root.left, root); } // 记录右孩子的父结点 if (root.right ! null) { parent.put(root.right, root); } // 递归处理左子树 buildCache(root.left); // 递归处理右子树 buildCache(root.right); } }