在二叉树中找到两个节点的最近公共祖先（C++）

  给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

数据范围：树上节点数满足1≤n≤10⁵ , 节点值val满足区间 [0,n)

要求：时间复杂度 O(n)

注：本题保证二叉树中每个节点的val值均不相同。

如当输入{3,5,1,6,2,0,8,#,#,7,4},5,1时，二叉树{3,5,1,6,2,0,8,#,#,7,4}如下图所示：

  所以节点值为5和节点值为1的节点的最近公共祖先节点的节点值为3，所以对应的输出为3。

注意：节点本身可以视为自己的祖先。

输入：
{3,5,1,6,2,0,8,#,#,7,4},5,1
返回值：
3

输入：
{3,5,1,6,2,0,8,#,#,7,4},2,7
返回值：
2

使用深度遍历（仅仅只是一开始默认向左子树深度搜索，然后到底部之后转向右子树，直至左右子树均搜索之后强制返回到上一节点），当找到o1或者o2时，分别记录其当前节点的所有父类，最后比较两个数据，得到最近的公共父节点。

class Solution {
public:
    
    
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        vector arro1;
        vector arro2;
        vector arr;
        stack stacks;
        bool left = false;
        bool right = false;
        while(root || !stacks.empty())
        {
            while(root)
            {
                stacks.push(root);
                arr.push_back(root->val);
                if(root->val == o1 && left == false)
                {
                    arro1.assign(arr.begin(),arr.end());
                    left = true;
                }
                if(root->val == o2 && right == false)
                {
                    arro2.assign(arr.begin(),arr.end());
                    right = true;
                }
                root = root->left?root->left:root->right;
            }
            
            root = stacks.top();
            stacks.pop();
            arr.pop_back();
            if(!stacks.empty() && stacks.top()->left == root)
                root = stacks.top()->right;
            else
                root = nullptr;
        }
        int res = 0;
        if(arro1.size()>=arro2.size())
        {
            for(int i =arro2.size()-1;i>=0;i--)
            {
                auto iter = find(arro1.begin(),arro1.end(),arro2[i]);
                if(iter!=arro1.end())
                {
                    res = arro2[i];
                    break;
                }
            }
        }
        else
        {
            for(int i =arro1.size()-1;i>=0;i--)
            {
                auto iter = find(arro2.begin(),arro2.end(),arro1[i]);
                if(iter!=arro2.end())
                {
                    res = arro1[i];
                    break;
                }
            }
        }
        return res;
    }
};

通过递归方式进行查询查找，但是时间复杂度过高，运行会超时，仅供参考。

class Solution {
public:
    
    
    bool GetDepth(TreeNode* node,int o1,int o2)
    {
        if(node == nullptr)return false;
        if(node->val == o1 || node->val == o2)
            return true;
        return GetDepth(node->left, o1, o2) || GetDepth(node->right, o1, o2);
    }
    
    int FatherNode(TreeNode* node,int o1,int o2)
    {
        if(node == nullptr)return 0;
        //以下情况为有一个带查找节点为父节点
        if(node->val == o1 && (GetDepth(node->left, o1, o2) || GetDepth(node->right, o1, o2)))
            return o1;
        
        if(node->val == o2 && (GetDepth(node->left, o1, o2) || GetDepth(node->right, o1, o2)))
            return o2;
        
        //左子树没找到，则全在右子树上
        if(!GetDepth(node->left, o1, o2))
            return FatherNode(node->right,o1,o2);
        //右子树没找到，则全在左子树上
        if(!GetDepth(node->right, o1, o2))
            return FatherNode(node->left,o1,o2);
        return node->val;
    }

    
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) 
    {
        return FatherNode(root,o1,o2);
    }
};