Lowest Common Ancestor III -1.png
Lowest Common Ancestor III -2.png
解題思路 ：
跟普通找 LCA 的差別就是 題目給的 ＡＢ兩點可能根本不在樹裡面 所以另外設(shè)定 boolean 檢查是否真的找到 A 或 B 點 如果有一點沒找到的話 就從找到的另一點往下搜尋看看是否有包含沒找到的點
C++ code :
<pre><code>
/**
- Definition of TreeNode:
- class TreeNode {
- public:
int val;TreeNode *left, *right;TreeNode(int val) {this->val = val;this->left = this->right = NULL;}- }
*/
class Solution {
public:
/**
* @param root: The root of the binary tree.
* @param A and B: two nodes
* @return: Return the LCA of the two nodes.
*/
TreeNode *LCA(TreeNode* root, TreeNode* A, TreeNode* B, bool &findA, bool &findB)
{
if(!root) return root;
if(root == A){
findA = true;
return root;
}
if(root == B){
findB = true;
return root;
}
TreeNode *left = LCA(root->left, A, B, findA, findB);
TreeNode *right = LCA(root->right, A, B, findA, findB);
if(left && right) return root;
return left? left : right;
}
bool search(TreeNode *res, TreeNode *n)
{
if(res == nullptr) return false;
if(res == n) return true;
return search(res->left, n) || search(res->right, n);
}
TreeNode *lowestCommonAncestor3(TreeNode* root, TreeNode* A, TreeNode* B) {
// write your code here
bool findA = false, findB = false;
TreeNode *res = LCA(root, A, B, findA, findB);
bool check = true;
if(!findA || !findB)
{
if(res == A) check = search(res, B);
else check = search(res, A);
}
return check? res : nullptr;
}
};
