236 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:

/**
 * 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:
    TreeNode* lca = NULL;
    int visited(TreeNode* root, TreeNode* p, TreeNode* q) {
        if ( root == NULL ) return 0;
        int left = visited(root->left, p, q);
        int right = visited(root->right, p, q);
        if ( left == 2 or right == 2 ) return 2;
        if ( left == 1 and right == 1 ) {lca = root; return 2;}
        if ( left + right == 1 and (root == p or root == q) ) {lca = root; return 2;}
        if ( left + right == 1 ) return 1;
        if ( left + right == 0 and (root == p or root == q) ) return 1;
        return 0;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        visited(root, p, q);
        return lca;
    }
};

class Solution(object):
  def dfs(self, root, p, q, visit_tag):
    sol = Solution()
    visit_tag_left, visit_tag_right = [0], [0]
    if ( root.left != None ):
      tmp = sol.dfs(root.left, p, q, visit_tag_left)
      visit_tag[0] += visit_tag_left[0]
      if ( tmp != None ): return tmp
      #if ( visit_tag_left[0] == 2 ): return root.left
      if ( visit_tag_left[0] == 1 and (root == p or root == q) ): return root
    if ( root.right != None ):
      tmp = sol.dfs(root.right, p, q, visit_tag_right)
      visit_tag[0] += visit_tag_right[0]
      if ( tmp != None ): return tmp
      #if ( visit_tag_right[0] == 2 ): return root.right
      if ( visit_tag_right[0] == 1 and (root == p or root == q) ): return root
    if ( root == p or root == q ): visit_tag[0] += 1
    if ( visit_tag[0] == 2 ): return root
    else: return None

  def lowestCommonAncestor(self, root, p, q):
    """
    :type root: TreeNode
    :type p: TreeNode
    :type q: TreeNode
    :rtype: TreeNode
    """
    sol = Solution()
    visit_tag = [0]
    return sol.dfs(root, p, q, visit_tag)

/**
 * 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:
    TreeNode* LCA = NULL;
    int visited(TreeNode* root, TreeNode* p, TreeNode* q) {
        if ( root == NULL ) return 0;
        int left = visited(root->left, p, q);
        int right = visited(root->right, p, q);
        if ( left == 2 or right == 2 ) return 2;
        int res = left + right + (root == p or root == q);
        if ( res == 2 ) LCA = root; 
        return res;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        visited(root, p, q);
        return LCA;
    }
};