题解27 | 递归非递归方法#二叉树中找两节点的最近公祖先#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    TreeNode * LCA(TreeNode* root, int o1, int o2){
        if(root == NULL || root->val == o1 || root->val == o2){
            return root;
        }
        TreeNode *l = LCA(root->left, o1, o2);
        TreeNode *r = LCA(root->right, o1, o2);

        if(l != NULL && r != NULL) {
            return root;
        }
        if(l != NULL) {
            return l;
        }
        if(r != NULL) {
            return r;
        }
        //都空的话
        return NULL;
    }
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        TreeNode * anc = LCA(root,o1,o2);
        return anc->val;
    }

};

算法基本思想：

①在函数LCA中，我们首先判断当前节点是否为空或者等于o1或o2的值，如果是的话，直接返回当前节点。然后递归调用左子树和右子树，得到它们的返回结果。根据左右子树的返回结果，可以确定最近公共祖先节点的位置。如果左右子树的返回结果都不为空，则当前节点为最近公共祖先节点。如果只有左子树的返回结果不为空，则左子树的返回结果为最近公共祖先节点。如果只有右子树的返回结果不为空，则右子树的返回结果为最近公共祖先节点。如果左右子树的返回结果都为空，则返回空。

②最后，在函数lowestCommonAncestor中，我们调用LCA函数来获取最近公共祖先节点，并返回其值。

时间复杂度：

这个算法的时间复杂度是O(N)，其中N是二叉树中的节点数。因为每个节点都会被访问一次，所以总共需要遍历所有的节点。

空间复杂度：

空间复杂度是O(H)，其中H是二叉树的高度。在递归调用中，需要使用系统栈来保存递归调用的上下文，所以空间复杂度取决于递归的深度，即二叉树的高度。

补充：递归实现

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * @param root TreeNode类 
 * @param p int整型 
 * @param q int整型 
 * @return int整型
 */
int lowestCommonAncestor(struct TreeNode* root, int p, int q ) {
    // write code here 3<=节点总数<=10000 非递归设立路径数组的参见C++方法
    if (p > root->val && q < root->val || p < root->val && q > root->val) {
        return root->val;
    }
    else if (p < root->val && q < root->val) {
        return lowestCommonAncestor(root->left, p, q);
    }
    else if (p > root->val && q > root->val) {
        return lowestCommonAncestor(root->right, p, q);
    }
    //任何p、q有与根节点值相同的情况直接返回根节点值
    return root->val;
}

基本算法思想：

1. 首先判断p和q与根节点root的值的关系，如果p和q分别位于root的左右子树，或者其中一个等于root的值，那么root就是最近的公共祖先节点，直接返回root的值。

2. 如果p和q都小于root的值，说明p和q都位于root的左子树中，那么递归调用函数，传入root的左子节点和p、q的值，继续在左子树中寻找最近公共祖先节点。

3. 如果p和q都大于root的值，说明p和q都位于root的右子树中，那么递归调用函数，传入root的右子节点和p、q的值，继续在右子树中寻找最近公共祖先节点。

时间复杂度：

在最坏情况下，如果树是一个完全不平衡的二叉搜索树，即树的高度为N（节点总数），那么最坏情况下，每次递归调用只能排除一个节点，需要遍历整个树才能找到最近公共祖先节点。所以时间复杂度是O(N)。

空间复杂度：

递归调用的空间复杂度取决于递归的深度，即树的高度。在最坏情况下，如果树是一个完全不平衡的二叉搜索树，递归的深度为N，所以空间复杂度是O(N)。