题目描述

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

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

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

题解

这道题的思想是转换为求两个链表的最后一个公共节点。

首先通过深度优先遍历找到二叉树中包含节点p的路径和包含节点q的路径，存入链表中。

然后遍历链表，找到最后一个公共节点，就是二叉树中两个节点的最近公共祖先了。

下面是参考代码：

class Solution {
    LinkedList<LinkedList<TreeNode>> list = new LinkedList<>();

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 对树遍历两遍，找到包含p和q的两条路径，然后再对两条路径找最后一个相同的节点。
        dfs(root, p, new LinkedList<TreeNode>());
        dfs(root, q, new LinkedList<TreeNode>());
        LinkedList<TreeNode> list1 = list.get(0);
        LinkedList<TreeNode> list2 = list.get(1);

        int i = 0, j = 0;
        while (i < list1.size() && j < list2.size()) {
            if (list1.get(i++) != list2.get(j++))
                return list1.get(i-2);
        }
        return list1.get(i-1);
    }

    public void dfs(TreeNode root, TreeNode target, LinkedList<TreeNode> path) {
        path.add(root);
        if (root.val == target.val) {
            list.add(new LinkedList<>(path));
            return;
        }
        if (root.left != null)
            dfs(root.left, target, path);
        if (root.right != null)
            dfs(root.right, target, path);
        path.remove(path.size()-1);
    }
}