题解 | #在二叉树中找到两个节点的最近公共祖先#

方法一

通过深度优先遍历，分别找出从根到两个结点的路径， 如1-2-3和1-2-5，那么路径的相同部分1-2的最后一个结点2即是最近祖先

方法二

递归考虑：

如果当前结点为空，返回空；否则看当前结点是否为两个结点中的一个，只要是，那么当前结点一定是最近祖先，否则，递归左树：

1. 左树中没找到，递归右树，答案一定在右树。
2. 左树中找到了，递归右树，右树中没找到，返回左树找到的；右树中找到了，返回当前结点

说明：方法一更直观，实现也很简单，效率略低，代码略长；方法二要站在宏观角度考虑，很精简。

程序按方法二实现

class Solution {
public:    
    TreeNode* dfsSearch(TreeNode* root, int o1, int o2) {
        if (!root || root->val == o1 || root->val == o2)
        {
            return root;
        }

        TreeNode *left = dfsSearch(root->left, o1, o2);

        if (left)
        {            
            TreeNode *right = dfsSearch(root->right, o1, o2);
            if (!right)
            {
                return left;
            }
            return root;
        }

        return dfsSearch(root->right, o1, o2);
    }
     
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {     
        return dfsSearch(root, o1, o2)->val;
    }
};