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

非递归方式--深度优先搜索
思路很简单，深度搜索出所有路径，搜索的过程中过滤出到达o1和o2的路径保存，最后找到o1和o2的路径上的公共节点

map<TreeNode, bool> m; 记录哪个节点访问过
deque<TreeNode> dq; 用于保存深度搜索路径
vector<deque<TreeNode*>> res; 用于保存搜索到o1或者o2时的路径

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        return dfs(root, o1, o2);
    }
    int dfs(TreeNode* root, int o1, int o2) {
        vector<deque<TreeNode*>> res;
        map<TreeNode*, bool> m;
        deque<TreeNode*> dq;
        dq.push_back(root);
        m[root] = true;
        while (!dq.empty()) {
            TreeNode* cur = dq.back();
            if (cur->left && m.find(cur->left) == m.end()) {
                dq.push_back(cur->left);
                m[cur->left] = true;
                if (cur->left->val == o1 || cur->left->val == o2)
                    res.push_back(dq);
                continue;
            }
            if (cur->right && m.find(cur->right) == m.end()) {
                dq.push_back(cur->right);
                m[cur->right] = true;
                if (cur->right->val == o1 || cur->right->val == o2)
                    res.push_back(dq);
                continue;
            }
            //回溯
            do  {
                dq.pop_back();
                if(!dq.empty())
                    cur = dq.back();
            } while (!dq.empty()&&
                m.find(cur->left)!= m.end()&&
                m.find(cur->right) != m.end());
        }
        //获取公共节点
        TreeNode* end_res = nullptr;
        while (res[0].front() == res[1].front()) {
            end_res = res[0].front();
            res[0].pop_front();
            res[1].pop_front();
        }
        return end_res->val;
    }
};