categories:[Blog,算法]

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

难度中等
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：
236. 二叉树的最近公共祖先 - 图1
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5和节点 1的最近公共祖先是节点 3 。
示例 2：
236. 二叉树的最近公共祖先 - 图2
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5和节点 4的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.     Map<Integer, TreeNode> parent = new HashMap<Integer, TreeNode>();
  12.     Set<Integer> visited = new HashSet<Integer>();
  14.     public void dfs(TreeNode root) {
  15.         if (root.left != null) {
  16.             parent.put(root.left.val, root);
  17.             dfs(root.left);
  18.         }
  19.         if (root.right != null) {
  20.             parent.put(root.right.val, root);
  21.             dfs(root.right);
  22.         }
  23.     }
  25.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  26.         dfs(root);
  27.         while (p != null) {
  28.             visited.add(p.val);
  29.             p = parent.get(p.val);
  30.             //visited.add(p.val);
  31.         }
  32.         while (q != null) {
  33.             if (visited.contains(q.val)) {
  34.                 return q;
  35.             }
  36.             q = parent.get(q.val);
  37.         }
  38.         return null;
  39.     }
  41. // 作者：LeetCode-Solution
  42. // 链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/er-cha-shu-de-zui-jin-gong-gong-zu-xian-by-leetc-2/
  43. // 来源：力扣（LeetCode）
  44. // 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
  45. }

解析

存储父节点
思路
我们可以用哈希表存储所有节点的父节点，然后我们就可以利用节点的父节点信息从 p 结点开始不断往上跳，并记录已经访问过的节点，再从 q 节点开始不断往上跳，如果碰到已经访问过的节点，那么这个节点就是我们要找的最近公共祖先。
算法
从根节点开始遍历整棵二叉树，用哈希表记录每个节点的父节点指针。
从 p 节点开始不断往它的祖先移动，并用数据结构记录已经访问过的祖先节点。
同样，我们再从 q 节点开始不断往它的祖先移动，如果有祖先已经被访问过，即意味着这是 p 和 q 的深度最深的公共祖先，即 LCA 节点。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/er-cha-shu-de-zui-jin-gong-gong-zu-xian-by-leetc-2/