Lowest Common Ancestor

Description

Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes.

The lowest common ancestor is the node with largest depth which is the ancestor of both nodes.

Notice
Assume two nodes are exist in tree.

Example
For the following binary tree:
  4
 / \
3   7
   / \
  5   6
LCA(3, 5) = 4
LCA(5, 6) = 7
LCA(6, 7) = 7

Added Hint:(maybe cause issue)

• every node is unqiue
• if we search LCA based on the node->value,
  what happened?

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

/**
 * 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 search tree.
     * @param A and B: two nodes in a Binary.
     * @return: Return the least common ancestor(LCA) of the two nodes.
     */
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *A, TreeNode *B) {
        // write your code here
        if (!root) {
           return NULL;
        }
        // if root is the LCA
        if (root == A || root == B) {
            return root;
        }
        // finding the rest
        // divide
        TreeNode* left = lowestCommonAncestor(root->left, A, B);
        TreeNode* right = lowestCommonAncestor(root->right, A, B);
        // judgement for the LCA
        // conquer
        // left and right find the A or B
        if (left && right) {
            return root;
        }
        // left cannot find A or B, but right find
        if (!left && right) {
            return right;
        }
        // right cannot find A or B, but left find
        if (left && !right) {
            return left;
        }
        return NULL;
    }
};

Similar problems

x

Tags

x