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

问题描述

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

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:

最低的共同祖先（LCA）是图论的一个概念和   计算机科学。设T是有n个节点的根树。最低的   共同祖先之间两个节点v和w定义为最低的   同时具有V和W的后代（在这里我们允许节点节点T中   是其自身的后代）。

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).

所以，是根据这个定义去正确的答案应该是 6 。如果这是一个面试问题将是很好事先与面试官澄清。

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屋！