熊二 | C++ | #农场牛群族谱#

题目考察的知识点

• 二叉树
• 递归

题目解答方法的文字分析

1. 如果左右两颗子树都有结果，说明root是更优的ans
2. 左边的子树包含了p或者q
3. 右边的子树包含了p或者q
4. 如果遍历到空的节点，函数直接返回-1

本题解析所用的编程语言

• cpp

完整且正确的编程代码

class Solution {
public:
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        if (root == nullptr) return -1;
        if (root->val == p || root->val == q) return root->val;

        int leftT = lowestCommonAncestor(root->left, p, q);
        int rightT = lowestCommonAncestor(root->right, p, q);
        if (leftT!=-1 && rightT!=-1) {// 如果左右两颗子树都有结果，说明root是更优的ans
            return root->val;
        }
        if (leftT!=-1) return leftT;// 左边的子树包含了p或者q
        return rightT;// 右边的子树包含了p或者q
    }
};

EOF