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


categories:[Blog,算法]


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

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

示例 1:

输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出:3
解释:节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    Map<Integer, TreeNode> parent = new HashMap<Integer, TreeNode>();
    Set<Integer> visited = new HashSet<Integer>();

    public void dfs(TreeNode root) &#123;
        if (root.left != null) &#123;
            parent.put(root.left.val, root);
            dfs(root.left);
        &#125;
        if (root.right != null) &#123;
            parent.put(root.right.val, root);
            dfs(root.right);
        &#125;
    &#125;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) &#123;
        dfs(root);
        while (p != null) &#123;
            visited.add(p.val);
            p = parent.get(p.val);
            //visited.add(p.val);
        &#125;
        while (q != null) &#123;
            if (visited.contains(q.val)) &#123;
                return q;
            &#125;
            q = parent.get(q.val);
        &#125;
        return null;
    &#125;

// 作者: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/
// 来源:力扣(LeetCode)
// 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
&#125;

解析

存储父节点
思路
我们可以用哈希表存储所有节点的父节点,然后我们就可以利用节点的父节点信息从 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/


文章作者:   future
版权声明:   本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 future !
 上一篇
54. 螺旋矩阵 54. 螺旋矩阵
categories:[Blog,算法] 54. 螺旋矩阵难度中等给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。 示例 1:输入:matrix = [[1,2,3],[4,5,6],[7,
2021-02-28 future
下一篇 
todo todo
236. 二叉树的最近公共祖先     236. 二叉树的最近公共祖先208. 实现 Trie (前缀树)         208. 实现 Trie (前缀树)62. 不同路径                     62. 不同路径46.
2021-02-28 future
  目录