235.lowest-common-ancestor-of-a-binary-search-tree.cpp

/*
 * @lc app=leetcode id=235 lang=cpp
 *
 * [235] Lowest Common Ancestor of a Binary Search Tree
 *
 * https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/
 *
 * algorithms
 * Easy (43.45%)
 * Total Accepted:    258.5K
 * Total Submissions: 594.6K
 * Testcase Example:  '[6,2,8,0,4,7,9,null,null,3,5]\n2\n8'
 *
 * Given a binary search tree (BST), find the lowest common ancestor (LCA) of
 * two given nodes in the BST.
 *
 * According to the definition of LCA on Wikipedia: “The lowest common ancestor
 * is defined between two nodes p and q as the lowest node in T that has both p
 * and q as descendants (where we allow a node to be a descendant of itself).”
 *
 * Given binary search tree:  root = [6,2,8,0,4,7,9,null,null,3,5]
 *
 *
 *
 * Example 1:
 *
 *
 * Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
 * Output: 6
 * Explanation: The LCA of nodes 2 and 8 is 6.
 *
 *
 * Example 2:
 *
 *
 * Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
 * Output: 2
 * Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant
 * of itself according to the LCA definition.
 *
 *
 *
 *
 * Note:
 *
 *
 * All of the nodes' values will be unique.
 * p and q are different and both values will exist in the BST.
 *
 *
 */

#include <stack>
#include <set>
using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution
{
  public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
    {
        stack<TreeNode *> st;
        stack<TreeNode *> pst;
        stack<TreeNode *> qst;
        set<TreeNode *> v;
        if (root)
            st.push(root);
        while (!st.empty())
        {
            TreeNode *c = st.top();
            v.insert(c);
            if (c->val == p->val)
                pst = st;
            if (c->val == q->val)
                qst = st;
            if (!qst.empty() && !pst.empty())
                break;
            if (c->left && v.find(c->left) == v.end())
                st.push(c->left);
            else if (c->right && v.find(c->right) == v.end())
                st.push(c->right);
            else
                st.pop();
        }
        stack<TreeNode *> tmp;
        while (!pst.empty())
        {
            tmp.push(pst.top());
            pst.pop();
        }
        tmp.swap(pst);
        while (!qst.empty())
        {
            tmp.push(qst.top());
            qst.pop();
        }
        tmp.swap(qst);
        TreeNode *ancestor;
        while (!pst.empty() && !qst.empty() && pst.top() == qst.top())
        {
            ancestor = pst.top();
            pst.pop();
            qst.pop();
        }
        return ancestor;
    }
};