题解 | #在二叉树中找到两个节点的最近公共祖先#

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    TreeNode* traversal(TreeNode* cur, int num1, int num2){
        // 递归终止条件
        if(!cur) return NULL;
        if(cur->val == num1 || cur->val == num2) return cur;
        // 后序遍历
        TreeNode* left = traversal(cur->left, num1, num2);  // 左
        TreeNode* right = traversal(cur->right, num1, num2);    // 右
        // 中
        if(!left) return right;
        if(!right) return left;
        return cur;
    }
    // TreeNode* LCA(TreeNode* r, int o1, int o2) {
    //     if (!r) return NULL;
    //     if (r->val == o1 || r->val == o2) return r;
 
    //     TreeNode* ln = LCA(r->left, o1, o2);
    //     TreeNode* rn = LCA(r->right, o1, o2);
 
    //     if (!ln) return rn;
    //     if (!rn) return ln;
 
    //     return r;
    // }
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        TreeNode* result = traversal(root, o1, o2);
        return result->val;
        // TreeNode* lca = LCA(root, o1, o2);
        // return lca->val;
    }
};