leetCode-236:Lowest Common Ancestor of a Binary Tree

问题描述

给定一个二叉树和两个节点，要求找出这两个节点的最近公共祖先。题目链接：**点我**

样例输入输出

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

树的形状如下

输出：3

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4

树的形状如下

输出：5

问题解法

遍历树，记录每个节点的父节点，然后从 p 节点往上找，将 p 节点的所有父节点放入 set 中，再从 q 节点往上找，最先遇到存在 set 中的父节点，就是要找的最近公共祖先。代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
    {
        Map<TreeNode, TreeNode> parentMap = new HashMap<>();
        dfs(root.left, root, parentMap);
        dfs(root.right, root, parentMap);
        
        Set<TreeNode> ancestors = new HashSet<>();
        TreeNode current = p;
        while (current != null)
        {
            ancestors.add(current);
            current = parentMap.get(current);
        }
        
        current = q;
        while (current != null)
        {
            if (ancestors.contains(current))
            {
                return current;
            }
            current = parentMap.get(current);
        }
        
        return null;
    }

    private void dfs(TreeNode root, TreeNode parent, Map<TreeNode, TreeNode> parentMap)
    {
        if (root == null)
        {
            return;
        }

        parentMap.put(root, parent);
        dfs(root.left, root, parentMap);
        dfs(root.right, root, parentMap);
    }
}