Leetcode.326.LCA of Binary Tree

题目

给定义一个二叉树，找到二叉树的LCA(最小公共祖先)。

    3
   /  \
  5     1
 / \   / \
 6  2  0  8
   / \
  7   4
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5

思路1

DFS。分别找到节点的路径，然后比较相等的节点。

bool lcapPath(TreeNode* root, TreeNode* p, vector<TreeNode*>& path) {
    if (!root) return false;
    path.push_back(root);
    if (root == p || lcapPath(root->left, p, path) || lcapPath(root->right, p, path)) {
        return true;
    }
    path.pop_back();
    return false;
}

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    vector<TreeNode*> pVec;
    lcapPath(root, p, pVec);
    vector<TreeNode*> qVec;
    lcapPath(root, q, qVec);

    TreeNode* res = nullptr;
    for (int i = 0; i < min(pVec.size(),qVec.size()); i++) {
        if (pVec[i] == qVec[i]) {
            res = pVec[i];
        }
    }
    return res;
}

思路2

递归。

TreeNode * lowestCommonAncestor(TreeNode * root, TreeNode * A, TreeNode * B) {
    if(root == NULL || root == A || root == B) return root;

    TreeNode *l = lowestCommonAncestor(root->left,A,B);
    TreeNode *r = lowestCommonAncestor(root->right,A,B);
    if(l && r) return root;
    return l?l:r;
}

思路3

循环。

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == nullptr)
        return root;
    stack<TreeNode*> s;
    vector<TreeNode*> vec; // p和q的公共祖先
    bool tag1 = false; // true:找到p
    bool tag2 = false; // true:找到q
    s.push(root);
    TreeNode* lastRoot = root;
    while (!s.empty()) // lastRoot(区分从左/右孩子返回)
    {
        root = s.top();
        if (root == p) {
            if(tag1 == false && tag2 == false)
                vec.push_back(root);
            tag1 = true;
        }
        else if (root == q) {
            if (tag2 == false && tag1 == false)
                vec.push_back(root);
            tag2 = true;
        }
        if (!tag1 && !tag2)
            vec.push_back(root); // 公共祖先入vector
        // 找到p,q并且root在公共祖先数组中
        if (tag1 && tag2 && find(vec.begin(), vec.end(), root) != vec.end())
            return root;
        // root的孩子节点还没访问
        if (lastRoot != root->right)
        {
            if (lastRoot != root->left) {
                if (root->left != nullptr) {
                    s.push(root->left);
                    continue;
                }
            }
            if (root->right != nullptr) {
                s.push(root->right);
                continue;
            }
        }
        // 孩子节点访问完，弹栈向上回溯
        lastRoot = root;
        s.pop();
    }
    return nullptr;
}

总结

DFS博大精深。