【LeetCode-简单】剑指 Offer 68 - II. 二叉树的最近公共祖先（C++实现）

文章目录

• 题目链接
• 解题思路
• 实现代码（C++）

题目链接

剑指 Offer 68 - II. 二叉树的最近公共祖先

解题思路

题目问的是二叉树最近的公共祖先。

可以用 DFS ，先分别递归查找以当前节点为根节点的树中，是否存在 p->val 和 q->val 。

 bool dfs(TreeNode *root, int val) {
     if (root != NULL) {
         if (root->val == val) {
             return true;
         }
         return dfs(root->left, val) || dfs(root->right, val);
     }
     return false;
 }

然后通过层序遍历，按照上面的方法，来处理整棵树。

由于层序遍历本就是按照深度（越深的在越后边）来遍历的，所以最后一个符合条件的，就是这两个节点的最近公共祖先。

实现代码（C++）

class Solution {
public:

    bool dfs(TreeNode *root, int val) {
        if (root != NULL) {
            if (root->val == val) {
                return true;
            }
            return dfs(root->left, val) || dfs(root->right, val);
        }
        return false;
    }

    TreeNode *process(TreeNode *root, int val1, int val2) {
        TreeNode *ans, *temp;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            temp = q.front(); q.pop();
            if (dfs(temp, val1) && dfs(temp, val2)) {
                ans = temp;
            }
            if (temp->left != NULL) {
                q.push(temp->left);
            }
            if (temp->right != NULL) {
                q.push(temp->right);
            }
        }

        return ans;
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return process(root, p->val, q->val);
    }
};