Lowest Common Ancestor

    The lowest common ancestor is the node with largest depth which is the
    ancestor of both nodes.

    Example

    For the following binary tree:

    LCA(3, 5) =

    LCA(5, 6) = 7

    初次接触这种题可能会没有什么思路，在没有思路的情况下我们就从简单例子开始分析！首先看看3和5，这两个节点分居根节点4的两侧，如果可以从子节点往父节点递推，那么他们将在根节点4处第一次重合；再来看看5和，这两个都在根节点4的右侧，沿着父节点往上递推，他们将在节点7处第一次重合；最后来看看6和7，此时由于7是6的父节点，故7即为所求。从这三个基本例子我们可以总结出两种思路——自顶向下(从前往后递推)和自底向上(从后往前递推)。

    顺着上述实例的分析，我们首先看看自底向上的思路，自底向上的实现用一句话来总结就是——如果遍历到的当前节点是 A/B 中的任意一个，那么我们就向父节点汇报此节点，否则递归到节点为空时返回空值。具体来说会有如下几种情况：

    1. 当前节点即为两个节点中的一个，此时向父节点返回当前节点。

    根据此递归模型容易看出应该使用先序/后序遍历来实现。

    C++ Recursion From Bottom to Top

    源码分析

    结合例子和递归的整体思想去理解代码，在root == A || root == B后即层层上浮(自底向上)，直至找到最终的最小公共祖先节点。

    关于重复节点：由于这里比较的是元素地址，因此可以认为树中不存在重复元素，否则不符合树的数据结构。

    为了解决上述方法可能导致误判的情况，我们可以对返回结果添加计数器来解决。由于此计数器的值只能由子树向上递推，故应该用后序遍历。在类中添加私有变量较为方便, C++中的写法较为复杂，后续再优化。

    定义pair<TreeNode *, int> result(node, counter)表示遍历到某节点时的返回结果，返回的node表示LCA 路径中的可能的最小节点，相应的计数器counter则表示目前和A或者匹配的节点数，若计数器为2，则表示已匹配过两次，该节点即为所求，若只匹配过一次，还需进一步向上递推。表述地可能比较模糊，还是看看代码吧。

    Java

    • [^leetcode]: - 清晰易懂的题解和实现。
    • Lowest Common Ancestor of a Binary Tree Part II | LeetCode - 如果存在指向父节点的指针，我们能否有更好的解决方案？
    • - 第一种和第二种方法可以在知道父节点时使用，但第二种 Divide and Conquer 才是本题需要的思想（第二种解法可以轻易改成不需要 parent 的指针的）。