O(N) time solution for general Tree

• In fact, I didn't see BST at first... So I came up a solution which deals with any binary tree.

``````class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
pair<TreeNode*, int> res = findNode(root, p, q);
return res.first;
}
//return the ancestor node and the number of discovered node
pair<TreeNode*, int> findNode(TreeNode* node, TreeNode* p, TreeNode* q){
if (node == NULL) return pair<TreeNode*, int>(NULL, 0);
int cnt = 0;
if (node == p) cnt++;
if (node == q) cnt++; //p may equals q

pair<TreeNode*, int> left = findNode(node->left, p, q);
if (left.second == 2) return left;
else if (left.second + cnt == 2) return pair<TreeNode*, int>(node, 2);

pair<TreeNode*, int> right = findNode(node->right, p, q);
if (right.second == 2) return right;
else if (right.second + cnt == 2) return pair<TreeNode*, int>(node, 2);

if (left.second + right.second == 2) return pair<TreeNode*, int>(node, 2);
else if (left.second == 1) return left;
else if (right.second == 1) return right;

return pair<TreeNode*, int>(node, cnt);
}
};``````

• wow..at first I didn't see it was bst too, but I didn't figure out a solution for it

• if you like it, you can vote it then more people can see the solution:)
BTW, why does any one vote down to you...

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.