二叉树的最低共同祖先 [英] Lowest Common Ancestor of a Binary Tree

问题描述

这是一个受欢迎的访谈问题，我可以在这个主题上找到的唯一一篇文章来自 TopCoder的。对我来说不幸的是，从面试答案的角度来看，它看起来过于复杂。

This is a popular interview question and the only article I can find on the topic is one from TopCoder. Unfortunately for me, it looks overly complicated from an interview answer's perspective.

除了绘制两个节点的路径并推断出它之外，是否有更简单的方法可以做到这一点。祖先？ （这是一个很受欢迎的答案，但是面试问题的变化需要一个恒定的空间答案）。

Isn't there a simpler way of doing this other than plotting the path to both nodes and deducing the ancestor? (This is a popular answer, but there's a variation of the interview question asking for a constant space answer).

推荐答案

恒定空间回答:(虽然不一定有效）。

Constant space answer: (although not necessarily efficient).

有一个函数findItemInPath（int index，int searchId，Node root）

Have a function findItemInPath(int index, int searchId, Node root)

然后从0深度的树迭代，在两个搜索路径中找到第0个项目，第1个项目等。

then iterate from 0 .. depth of tree, finding the 0-th item, 1-th item etc. in both search paths.

当你找到我时这样函数返回两者的结果相同，但不是i + 1，
，那么路径中的第i项是最低共同祖先。

When you find i such that the function returns the same result for both, but not for i+1, then the i-th item in the path is the lowest common ancestor.

这篇关于二叉树的最低共同祖先的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！