『递归的妙用』题解 | #在二叉树中找到两个节点的最近公共祖先#

需要多做几遍的题目。。

• 『刚开始做的时候卡了。。。』
• 递归的妙用

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */



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

        if( nullptr==root ) return 0x3f3f3f;//表示没有公共祖先
        if( o1==root->val || o2==root->val )
        {
            return root->val;//当前节点就是最近公共祖先
        }
        //去左子树找最近公共祖先
        int Left=lowestCommonAncestor( root->left , o1,  o2);
        //去右边子树找最近公共祖先
        int Right=lowestCommonAncestor( root->right , o1, o2);

        if( 0x3f3f3f==Right ) return Left;
        if( 0x3f3f3f==Left ) return Right;
        return root->val;

    }
};