题目分析

有关树的题目，小伙伴们就要想到递归，这个要深深的印在脑海里面。本题和Leetcode 剑指Offer68-Ⅰ是姐妹类型，这个题目难度稍微大一些，上一题我没有拿出来讲解是因为过于简单。在二叉搜索树中查找，因为是搜索树，我们可以根据节点的大小选择固定的路，不用进行回溯，所以通过迭代即可，不用递归进行查找，**时间复杂度为$O(log(n))$。这个题目我们不知道树中节点的大小关系，因此需要进行递归查找，时间复杂度为$O(n)$**。

递归

在这里先给出我的笨方法，虽然时间复杂度和空间复杂度并不高，但是代码长度大，不美观。

我的思路是自底向上进行查找，当找到p或者q时，数量加1，当数量等于2时，说明该节点是最近的公共祖先。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

#include<iostream>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        int nums = 0;
        return subQuestion(root, p, q, nums);
    }

    TreeNode* subQuestion(TreeNode* root, TreeNode* p, TreeNode* q, int& nums) {
        if (!root) {
            return NULL;
        }
        int left = 0, right = 0;
        TreeNode* leftChild = subQuestion(root->left, p, q, left);
        TreeNode* rightChild = subQuestion(root->right, p, q, right);
        nums = left + right;
        if (root == p || root == q) {
            nums++;
        }
        if (left == 2) {
            return leftChild;
        }
        else if (right == 2) {
            return rightChild;
        }
        else {
            if (nums == 2) {
                return root;
            }
            else {
                return NULL;
            }
        }
    }
};

优化递归

要找两个节点的最近公共祖先，现在有三种情况，一个是两个节点都在某个节点的左孩子中，第二个是两个节点都存在于某个节点的右孩子中，第三个是两个节点一左一右分别存在于左孩子和右孩子中。

我们自底向上进行查找，当找到p或者q时返回p和q，p和q一定在某个节点的左右子树上，一个在左，一个在右，如果没有找到该节点，那么左右子树一定有一个是NULL，如果left = NULL，则return right，如果right = NULL，则return left，如果左右都不是NULL，说明找到了最近的公共祖先，返回root即可。

这个思路是比较难想的，代码却非常简单，也非常漂亮。算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

#include<iostream>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root == p || root == q) return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if (!left) return right;
        if (!right) return left;
        return root;
    }
};

刷题总结

这个题目作为简单题，我不能接受，我想了很久，用了一种很笨的方法，虽然也是自底向上，但是代码不优美，这里提醒小伙伴们在刷题的时候，不能提交没有问题就进行下一题，一定要看一看别人的思路和方法，多多学习，这样才可以更好的提升自己。