#include <gtest/gtest.h>
#include <iostream>
#include <leetcode/treenode.hpp>

using namespace std;

/**
 * This file is generated by leetcode_add.py v1.0
 *
 * 236.
 *      Lowest Common Ancestor of a Binary Tree
 *
 * ––––––––––––––––––––––––––––– Description –––––––––––––––––––––––––––––
 *
 *   Given a binary tree, find the lowest common ancestor (LCA) of two
 *   given nodes in the
 *   According to the <a
 *   href="https://en.wikipedia.org/wiki/Lowest_common_ancestor"
 *   target="_blank">definition of LCA on Wikipedia</a>: “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” ).”
 *
 * ––––––––––––––––––––––––––––– Constraints –––––––––––––––––––––––––––––
 *
 *   • The number of nodes in the tree is in the range ‘[2, 10⁵]’ .
 *   • ‘-10⁹ ≤ Node.val ≤ 10⁹’
 *   • All ‘Node.val’ are “unique” .
 *   • ‘p ≠ q’
 *   • ‘p’ and ‘q’ will exist in the tree.
 *
 */

struct q236 : public ::testing::Test {
  // Leetcode answer here
  class Solution {
   private:
    bool trace(TreeNode* root, TreeNode* p, vector<TreeNode*>& path) {
      if (root == nullptr) return false;
      path.push_back(root);
      if (root == p)
        return true;
      else if (trace(root->left, p, path) || trace(root->right, p, path))
        return true;
      path.pop_back();
      return false;
    }
   public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
      vector<TreeNode*> trace_p, trace_q;
      if (trace(root, p, trace_p) && trace(root, q, trace_q)) {
        TreeNode* res = nullptr;
        for (int i = 0; i < trace_p.size() && i < trace_q.size() && trace_p[i] == trace_q[i]; ++i) {
          res = trace_p[i];
        }
        return res;
      }
      return nullptr;
    }
  };

  class Solution *solution;
};

TEST_F(q236, sample_input01) {
  solution = new Solution();
  TreeNode* root = TreeNode::generate({3, 5, 1, 6, 2, 0, 8, NULL_TREENODE, NULL_TREENODE, 7, 4});
  TreeNode* p = TreeNode::generate({});
  TreeNode* q = TreeNode::generate({});
  TreeNode* exp = TreeNode::generate({});
  TreeNode* act = solution->lowestCommonAncestor(root, p, q);
  EXPECT_TREENODE_EQ(act, exp);
  TreeNode::release(root, p, q, exp, act);
  delete solution;
}

TEST_F(q236, sample_input02) {
  solution = new Solution();
  TreeNode* root = TreeNode::generate({3, 5, 1, 6, 2, 0, 8, NULL_TREENODE, NULL_TREENODE, 7, 4});
  TreeNode* p = TreeNode::generate({});
  TreeNode* q = TreeNode::generate({});
  TreeNode* exp = TreeNode::generate({});
  TreeNode* act = solution->lowestCommonAncestor(root, p, q);
  EXPECT_TREENODE_EQ(act, exp);
  TreeNode::release(root, p, q, exp, act);
  delete solution;
}

TEST_F(q236, sample_input03) {
  solution = new Solution();
  TreeNode* root = TreeNode::generate({1, 2});
  TreeNode* p = TreeNode::generate({});
  TreeNode* q = TreeNode::generate({});
  TreeNode* exp = TreeNode::generate({});
  TreeNode* act = solution->lowestCommonAncestor(root, p, q);
  EXPECT_TREENODE_EQ(act, exp);
  TreeNode::release(root, p, q, exp, act);
  delete solution;
}