二叉树的第一个公共祖先 [英] First Common Ancestor of a Binary Tree

问题描述

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

If I have a binary search tree like this then what will be lowest common ancestor of nodes 6 and 1?

推荐答案

根据维基百科定义的最低共同祖先我纠正自己:

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

最低共同祖先(LCA)是图论中的一个概念，计算机科学.设 T 是一棵有 n 个节点的有根树.最低的共同祖先在两个节点 v 和 w 之间定义为最低T 中同时具有 v 和 w 作为后代的节点(我们允许一个节点成为自己的后代).

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