The-Art-Of-Programming-By-July/03.03.md at master ・ julycoding/The-Art-Of-Programming-By-July ・ GitHub

The-Art-Of-Programming-By-July/03.03.md at master ・ julycoding/The-Art-Of-Programming-By-July ・ GitHub

最近公共祖先LCA问题 问题描述 求有根树的任意两个节点的最近公共祖先。 分析与解法 举个例子，如针对下图所示的一棵普通的二叉树来讲： 结点3和结点4的最近公共祖先是结点2，即LCA（3 4）=2 。在此，需要注意到当两个结点在同一棵子树上的情况，如结点3和结点2的最近公共祖先为2，即 LCA（3，2）=2。同理：LCA（5，6）=4，LCA（6，10）=1。 明确了题意，咱们便来试着解决这个问题。直观的做法，可能是针对是否为二叉查找树分情况讨论，这也是一般人最先想到的思路。除此之外，还有所谓的Tarjan算法、倍增算法、以及转换为RMQ问题（求某段区间的极值）。后面这几种算法相对高级，不那么直观，但思路比较有启发性，了解一下也有裨益。 解法一：暴力对待 1.1、是二叉查找树 在当这棵树是二叉查找树的情况下，如下图： 如果当前结点t 大于结点u、v，说明u、v都在t 的左侧，所以它们的共同祖先必定在t 的左子树中，故从t 的左子树中继续查找； 如果当前结点t 小于结点u、v，说明u、v都在t 的右侧，所以它们的共同祖先必定在t 的右子树中，故从t 的右子树中继续查找； 如果当前结点t 满足 u right) { int temp = left; left = right; right = temp; } while (true) { //如果t小于u、v，往t的右子树中查找 if (t.value < left) { parent = t; t = t.right; //如果t大于u、v，往t的左子树中查找 } else if (t.value > right) { parent = t; t = t.left;

Read full article from The-Art-Of-Programming-By-July/03.03.md at master ・ julycoding/The-Art-Of-Programming-By-July ・ GitHub