/**

  * 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: A TreeNode in a Binary.

      * @param B: A TreeNode 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 == NULL)    return NULL;

         if(root==A || root==B)  return root;

         //递归寻找A B在左右子树的位置

         TreeNode* left = lowestCommonAncestor(root->left,A,B);

         TreeNode* right = lowestCommonAncestor(root->right,A,B);

         //如果A B分别位于root的两侧，则root是他们的LCA，否则是左子树或者右子树

         if(left&&right) return root;

         return left?left:right;

     }

 };

 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

     if (root == nullptr)

         return root;

     stack<TreeNode*> s;

     vector<TreeNode*> vec; // p和q的公共祖先

     bool tag1 = false; // true:找到p

     bool tag2 = false; // true:找到q

     s.push(root);

     TreeNode* lastRoot = root;

     while (!s.empty()) // lastRoot(区分从左/右孩子返回)

     {

         root = s.top();

         if (root == p) {

             if(tag1 == false && tag2 == false)

                 vec.push_back(root);

             tag1 = true;

         }

         else if (root == q) {

             if (tag2 == false && tag1 == false)

                 vec.push_back(root);

             tag2 = true;

         }

         if (!tag1 && !tag2)

             vec.push_back(root); // 公共祖先入vector

         // 找到p,q并且root在公共祖先数组中

         if (tag1 && tag2 && find(vec.begin(), vec.end(), root) != vec.end())

             return root;

         // root的孩子节点还没访问

         if (lastRoot != root->right)

         {

             if (lastRoot != root->left) {

                 if (root->left != nullptr) {

                     s.push(root->left);

                     continue;

                 }

             }

             if (root->right != nullptr) {

                 s.push(root->right);

                 continue;

             }

         }

         // 孩子节点访问完，弹栈向上回溯

         lastRoot = root;

         s.pop();

     }

     return nullptr;

 }