LeetCode Q236: Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Solution 1:

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	void helper(TreeNode* root, TreeNode* p, TreeNode* q, unordered_map<TreeNode*, int>& myMap, TreeNode*& LCA) {
	if(root==NULL)
	return;
	if(root==p||root==q)
	myMap[root]=myMap[root]+1;
	unordered_map<TreeNode*, int>::const_iterator lit = myMap.find(root->left);
	if(lit==myMap.end())
	helper(root->left, p, q, myMap, LCA);
	unordered_map<TreeNode*, int>::const_iterator rit = myMap.find(root->right);
	if(rit==myMap.end())
	helper(root->right, p, q, myMap, LCA);
	myMap[root]=myMap[root]+myMap[root->left]+myMap[root->right];
	if(myMap[root]==2||(myMap[root->left]==1&&myMap[root->right]==1))
	LCA=LCA==NULL? root:LCA;
	}
	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q){
	unordered_map<TreeNode*, int> myMap;
	TreeNode* LCA=NULL;
	helper(root, p, q, myMap, LCA);
	return LCA;
	}
	};

view raw Q236LCA.cpp hosted with ❤ by GitHub

Solution 2:

	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
	if (!root || root == p || root == q) return root;
	TreeNode* left = lowestCommonAncestor(root->left, p, q);
	TreeNode* right = lowestCommonAncestor(root->right, p, q);
	return !left ? right : !right ? left : root;
	}

view raw Q236-2.cpp hosted with ❤ by GitHub

Round 2 solution:

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	int helper(TreeNode* root, TreeNode*& res, TreeNode* p, TreeNode* q){
	int count = 0;
	if(root==NULL)
	return count;
	if(root==p||root==q)
	count++;
	int l = helper(root->left, res, p, q);
	int r = helper(root->right, res, p, q);
	count +=l+r;
	if(count==2&&res==NULL)
	res=root;
	return count;
	}
	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
	TreeNode* res=NULL;
	if(root==NULL)
	return res;
	helper(root, res, p, q);
	return res;
	}
	};

view raw Q236Rnd2.cpp hosted with ❤ by GitHub