题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 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);
}
}
