思路:利用递归,当找到了o1或者o2时,返回true,否则返回false,当左子树与右子树都找到了目标,或者当前值为目标并且左右子树中含有目标时则将当前节点的值赋值给res,作为公共祖先。
/** * 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 val1; int val2; int res; bool inorder(TreeNode* root) { if(!root) { return false; } bool l = inorder(root->left); bool cur = root->val == val1 || root->val==val2; bool r = inorder(root->right); bool result = l||r||cur; if(l&&r || cur&&l || cur&&r) { res = root->val; result = false; } return result; } int lowestCommonAncestor(TreeNode* root, int o1, int o2) { // write code here val1 = o1; val2 = o2; inorder(root); return res; } };