二叉树的第一个共同的祖先 [英] first common ancestor of a binary tree

问题描述

我有疑问，如果我有一个这样的二叉搜索树，那么什么将是节点6和1的最低共同祖先。
感谢

解决方案

根据维基百科定义<一个href =http://en.wikipedia.org/wiki/Lowest_common_ancestor =nofollow>最低的共同祖先我纠正了自己：

最低的共同祖先（LCA）是图论和
计算机科学的概念。让T成为有n个节点的根树。最低的
共同祖先在两个节点v和w之间定义为T中最低的
节点，其中v和w都作为后代（，我们允许节点
成为本身的后代）。

所以是的，这个定义正确答案将是 6 。如果这是采访问题，那么很好地提前与面试官进行澄清。

I have a doubt that if i have a binary search tree like this then what will be lowest common ancestor of nodes 6 and 1.
Thanks

解决方案

According to the Wikipedia definition of the Lowest common ancestor I correct myself:

The lowest common ancestor (LCA) is a concept in graph theory and computer science. Let T be a rooted tree with n nodes. The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).

So yes going by this definition the correct answer would be 6. If this is an interview question would be good to clarify in advance with the interviewer.

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