Lowest Common Ancestor III(ladder)

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. Return null if LCA does not exist.

Notice
node A or node B may not 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

Link

Lintcode_ladder

Method

1. bfs to make sure A B existing, then find LCA
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 tree.
     * @param A and B: two nodes
     * @return: Return the LCA of the two nodes.
     */
    TreeNode *lowestCommonAncestor3(TreeNode* root, TreeNode* A, TreeNode* B) {
        // write your code here
        if (!root || !A || !B) {
            return nullptr;
        }
        if (!existing(root, A, B)) {
            return nullptr;
        }
        return helper(root, A, B);
    }
    // test A B existing
    bool existing(TreeNode* root, TreeNode* A, TreeNode* B) {
        // bfs searching
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            auto cur = q.front();
            q.pop();
            // test existing
            if (A && cur == A) {
                A = nullptr;
            }
            if (B && cur == B) {
                B = nullptr;
            }
            if (!A && !B) {
                return true;
            }
            // for next level
            if (cur->left) {
                q.push(cur->left);
            }
            if (cur->right) {
                q.push(cur->right);
            }
        }
        return false;
    }
    // find LCA
    TreeNode* helper(TreeNode* root, TreeNode* A, TreeNode* B) {
        if (!root) {
            return nullptr;
        }
        if (root == A || root == B) {
            return root;
        }
        // divide
        TreeNode* left = helper(root->left, A, B);
        TreeNode* right = helper(root->right, A, B);
        // conquer
        if (left && right) {
            return root;
        } else if (right) {
            return right;
        } else if (left) {
            return left;
        } else {
            return nullptr;
        }
    }
};

Similar problems

x

Tags

x