// 156. Binary Tree Upside Down
TreeNode* upsideDownBinaryTree(TreeNode* root) {
  if (!root || !root->left && !root->right) 
    return root;
  
  TreeNode* new_root = upsideDownBinaryTree(root->left);       
  
  root->left->left = root->right;
  root->left->right = root;
  root->left = nullptr;
  root->right = nullptr;
  
  return new_root;
}

// 426. Convert Binary Search Tree to Sorted Doubly Linked List
pair<Node*, Node*> ConnectToDoubleList(Node* root, bool flag) {
  if (!root) return {nullptr, nullptr};
  auto left = ConnectToDoubleList(root->left, false);
  if (left.second) {
    root->left = left.second;
    left.second->right = root;
  }
  auto right = ConnectToDoubleList(root->right, true);
  if (right.first) {
    root->right = right.first;
    right.first->left = root;
  }
  return {left.first?left.first:root, right.second?right.second:root};
}  
Node* treeToDoublyList(Node* root) {
  if (!root) return nullptr;
  ConnectToDoubleList(root, false);   
  Node* stt = root;
  Node* fin = root;
  while (stt->left) {
    stt = stt->left;
  }
  while (fin->right) {
    fin = fin->right;
  }
  stt->left = fin;
  fin->right = stt;
  return stt;
}

// 104. Maximum Depth of Binary Tree 
int maxDepth(TreeNode* root) { 
  if (root == nullptr) return 0; 
  return max(maxDepth(root->left), maxDepth(root->right)) + 1; 
} 

// 111. Minimum Depth of Binary Tree 
int minDepth(TreeNode* root) { 
  if (root == nullptr) return 0; 
  if (root->left == nullptr && root->right == nullptr) return 1; 
  return min(root->left?minDepth(root->left):INT_MAX,  
             root->right?minDepth(root->right):INT_MAX) + 1; 
} 

// 100. Same Tree 
bool isSameTree(TreeNode* p, TreeNode* q) { 
  if (p == nullptr && q == nullptr) return true; 
  if ((p == nullptr && q != nullptr) ||  
      (p != nullptr && q == nullptr) || 
      (p->val != q->val)) 
    return false; 
  return isSameTree(p->left, q->left) &&  
         isSameTree(p->right, q->right); 
} 

// 101. Symmetric Tree 
bool IsSymmetric(TreeNode* left, TreeNode* right) { 
  if (left == nullptr && right == nullptr) return true; 
  if ((left == nullptr && right != nullptr) || 
      (left != nullptr && right == nullptr) ||  
       (left->val != right->val)) 
    return false; 
  return IsSymmetric(left->left, right->right) &&  
         IsSymmetric(left->right, right->left); 
} 

bool isSymmetric(TreeNode* root) { 
  if (root == nullptr) return true; 
  return IsSymmetric(root->left, root->right); 
} 

// 98. Validate Binary Search Tree 
bool isValidBST(TreeNode* root,  
                double left_border = -DBL_MAX, 
                double right_border = DBL_MAX) { 
  if (root == nullptr) return true;
  if (root->val <= left_border || root->val >= right_border)  {
    return false; 
  } 
  return isValidBST(root->left, left_border, root->val) && 
         isValidBST(root->right, root->val, right_border); 
} 

// 110. Balanced Binary Tree. Use pari to store status and return value. 
pair<int, bool> IsBalanced(TreeNode* root) { 
  if (root == nullptr) return make_pair(0, true); 
  const auto [d1, s1] = IsBalanced(root->left); 
  if (!s1) return make_pair(d1, false); 
  const auto [d2, s2] = IsBalanced(root->right); 
  if (!s2) return make_pair(d2, false); 
  if (abs(d1 - d2) > 1) return make_pair(d1, false); 
  return make_pair(max(d1, d2) + 1, true); 
} 

bool isBalanced(TreeNode* root) { 
  const auto [depth, status] = IsBalanced(root); 
  return status; 
} 

// 222. Count Complete Tree Nodes 
// Method 1 
int countNodes(TreeNode* root) { 
  if (root == nullptr) return 0; 
  return countNodes(root->left) + countNodes(root->right) + 1; 
} 

// Method 2 
int countNodes(TreeNode* root) { 
  if (root == nullptr) return 0; 
  auto left = root; 
  int left_num = 0; 
  while (left != nullptr) { 
    ++left_num; 
    left = left->left; 
  } 
  auto right = root; 
  int right_num = 0; 
  while (right != nullptr) { 
    ++right_num; 
    right = right->right; 
  } 
  if (left_num == right_num) return pow(2, left_num) - 1; 
  return countNodes(root->left) + countNodes(root->right) + 1; 
} 

// 298. Binary Tree Longest Consecutive Sequence
int longestConsecutive(TreeNode* root) {
  const auto [cur_max, max_len] = LongestConsecutive(root);
  return max_len;
}  
pair<int, int> LongestConsecutive(TreeNode* root) {
  if (!root) return {0, 0};
  int root_l = 1; 
  auto [len_l, max_l] = LongestConsecutive(root->left);
  if (root->left && root->left->val == root->val + 1) {
    ++len_l;
    root_l = len_l;
  }
  max_l = max(len_l, max_l);
  auto [len_r, max_r] = LongestConsecutive(root->right);
  if (root->right && root->right->val == root->val + 1) {
    ++len_r;
    root_l = len_r;
  }
  max_r = max(len_r, max_r);
  return {root_l, max(max(max_l, max_r), root_l)};
}

// 250. Count Univalue Subtrees
pair<int, int> CountUnivalSubtrees(TreeNode* root) {
  if (!root) return {0, 0};
  if (!root->left && !root->right) {
    return {1, root->val};
  }
  auto [l_num, l_val] = CountUnivalSubtrees(root->left);
  auto [r_num, r_val] = CountUnivalSubtrees(root->right);
  if (!l_num) l_val = root->val;
  if (!r_num) r_val = root->val;
  if (root->val == l_val && root->val == r_val) {
    return {1 + l_num + r_num, root->val};
  } 
  return {l_num + r_num, 10000};
}  
int countUnivalSubtrees(TreeNode* root) {
  int count = 0;
  const auto [num, _] = CountUnivalSubtrees(root);
  return num;
}

// 333. Largest BST Subtree
int max_num = 0;

vector<int> FindLargestBSTSubtree(TreeNode* root) {
  if (!root) return {0, INT_MIN, INT_MIN};
  if (!root->left && !root->right) 
    return {1, root->val, root->val};
  vector<int> left = FindLargestBSTSubtree(root->left);
  vector<int> right = FindLargestBSTSubtree(root->right);
  max_num = max(max_num, max(left[0], right[0]));
  if (!left[0] && left[1] != INT_MIN) {
    return {0, 0, 0};
  }
  if (!right[0] && right[1] != INT_MIN) {
    return {0, 0, 0};
  }
  int new_num = 0;
  if ((root->val > left[2] || left[2] == INT_MIN) 
      && (root->val < right[1] || right[1] == INT_MIN)) {
    new_num = left[0] + right[0] + 1; 
  }
  
  return {new_num, left[1] == INT_MIN?root->val:left[1], right[2] == INT_MIN?root->val:right[2]};
}  
  
int largestBSTSubtree(TreeNode* root) {
  const auto root_num = FindLargestBSTSubtree(root);
  return max(max_num, root_num[0]);
}

// 112. Path Sum 
bool hasPathSum(TreeNode* root, int sum) { 
  if (root == nullptr) return false; 
  if (root->left == nullptr && root->right == nullptr) { 
    return root->val == sum; 
  } 
  return hasPathSum(root->left, sum - root->val) || 
         hasPathSum(root->right, sum - root->val); 
} 

// 113. Path Sum II 
// Method 1 
vector<vector<int>> PathSum(TreeNode* root, int sum) { 
  if (root == nullptr) return {}; 
  if (root->left == nullptr && root->right == nullptr) { 
    if (root->val == sum) { 
      return ; 
    }  
    return {}; 
  } 
  vector<vector<int>> left_res = PathSum(root->left, sum - root->val); 
  vector<vector<int>> right_res = PathSum(root->right, sum - root->val); 
  vector<vector<int>> ans; 
  for (auto ele : left_res) { 
    ele.push_back(root->val); 
    ans.push_back(ele); 
  } 
  for (auto ele : right_res) { 
    ele.push_back(root->val); 
    ans.push_back(ele); 
  } 
  return ans; 
} 

vector<vector<int>> pathSum(TreeNode* root, int sum) { 
  auto ans = PathSum(root, sum); 
  for (auto& ele : ans) { 
    reverse(ele.begin(), ele.end()); 
  } 
  return ans; 
}  

// Method 2 
vector<vector<int>> ans; 
void PathSum(TreeNode* root, int sum, vector<int> nums) { 
  if (root == nullptr) return; 
  if (root->left == nullptr && root->right == nullptr) { 
    if (root->val == sum) { 
      nums.push_back(root->val); 
      ans.push_back(nums); 
    } 
    return; 
  } 
  nums.push_back(root->val); 
  PathSum(root->left, sum - root->val, nums); 
  PathSum(root->right, sum - root->val, nums); 
} 
vector<vector<int>> pathSum(TreeNode* root, int sum) { 
  PathSum(root, sum, {}); 
  return ans; 
}  

// 437. Path Sum III 
int PathSumHelper(TreeNode* root, int sum) { 
  if (root == nullptr) return 0; 
  return (root->val == sum) +  
         PathSumHelper(root->left, sum - root->val) +  
         PathSumHelper(root->right, sum - root->val); 
} 

int pathSum(TreeNode* root, int sum) { 
  if (root == nullptr) return 0; 
  return PathSumHelper(root, sum) +  
         pathSum(root->left, sum) +  
         pathSum(root->right, sum); 
} 

// 257. Binary Tree Paths | divide and conquer. 
vector<string> binaryTreePaths(TreeNode* root) { 
  if (root == nullptr) return {}; 
  if (root->left == nullptr && root->right == nullptr) { 
    return {to_string(root->val)}; 
  }  
  vector<string> left_res = binaryTreePaths(root->left); 
  vector<string> right_res = binaryTreePaths(root->right); 
  vector<string> ans; 
  string root_str = to_string(root->val); 
  for (const auto str : left_res) { 
    ans.push_back(root_str + "->" + str); 
  } 
  for (const auto str : right_res) { 
    ans.push_back(root_str + "->" + str);  
  } 
  return ans; 
} 

// 129. Sum Root to Leaf Numbers 
int sumNumbers(TreeNode* root, int cur_sum = 0) { 
  if (root == nullptr) return 0; 
  if (root->left == nullptr && root->right == nullptr) { 
    return cur_sum * 10 + root->val; 
  } 
  return sumNumbers(root->left, 10 * cur_sum + root->val) +  
         sumNumbers(root->right, 10 * cur_sum + root->val); 
} 

// 404. Sum of Left Leaves 
int sumOfLeftLeaves(TreeNode* root, int flag = 1) { 
  if (root == nullptr) return 0; 
  if (root->left == nullptr && root->right == nullptr) { 
    return flag == -1?root->val:0; 
  } 
  return sumOfLeftLeaves(root->left, -1) +  
         sumOfLeftLeaves(root->right, 1); 
} 

// 938. Range Sum of BST 
int rangeSumBST(TreeNode* root, int L, int R) { 
  if (root == nullptr) return 0; 
  const auto cur_val = root->val; 
  const bool in_range = cur_val >= L && cur_val <= R; 
  return ((cur_val > R || in_range)? rangeSumBST(root->left, L, R) : 0) + 
          ((cur_val < L || in_range)? rangeSumBST(root->right, L, R) : 0) + 
          (in_range ? cur_val : 0); 
} 

// 1302. Deepest Leaves Sum, map usage->map<int, int, greater<int>> 
map<int, int, greater<int>> record;  
int deepestLeavesSum(TreeNode* root, int level = 0) { 
  if (root == nullptr) { 
    return (record.size() > 0) ?record.begin()->second:0;  
   } 
   if (root->left == nullptr && root->right == nullptr) { 
     record[level] += root->val; 
     return record.begin()->second; 
   } 
   deepestLeavesSum(root->left, level + 1);   
   deepestLeavesSum(root->right, level + 1);     
   return record.begin()->second;   
} 

// 653. Two Sum IV - Input is a BST 
// Method 1 
unordered_set<int> record_; 
bool findTarget(TreeNode* root, int k) { 
  if (root == nullptr) return false; 
  if (record_.find(k - root->val) != record_.end()) return true; 
  record_.insert(root->val); 
  return findTarget(root->left, k) || findTarget(root->right, k); 
} 

// Methd 2 
vector<int> GetSequence(TreeNode* root) { 
  if (root == nullptr) return {}; 
  const int root_val = root->val; 
  vector<int> left_nums = GetSequence(root->left); 
  left_nums.push_back(root_val); 
  vector<int> right_nums = GetSequence(root->right); 
  left_nums.reserve(left_nums.size() + distance(right_nums.begin(), 
                    right_nums.end())); 
  left_nums.insert(left_nums.end(), right_nums.begin(),  
                   right_nums.end()); 
  return left_nums; 
} 

bool FindTwoSumTarget(const vector<int>& nums, int target) { 
  if (nums.size() < 2) return false; 
  int left_idx = 0; 
  int right_idx = nums.size() - 1; 
  while (left_idx < right_idx) { 
    const int cur_sum = nums[left_idx] + nums[right_idx]; 
    if (cur_sum < target) ++left_idx; 
    else if (cur_sum > target) --right_idx; 
    else return true; 
  } 
  return false; 
} 

bool findTarget(TreeNode* root, int k) { 
  const auto nums = GetSequence(root); 
  return FindTwoSumTarget(nums, k); 
} 

// Method 3: two recursive  
TreeNode* node = nullptr; 
bool Search(TreeNode* root, int k, TreeNode* tmp) { 
  if (root == nullptr) return false; 
  if (root->val == k) return root != tmp; 
  else if (root->val < k) return Search(root->right, k, tmp); 
  else return Search(root->left, k, tmp);   
} 

bool findTarget(TreeNode* root, int k) { 
  if (root != node && node == nullptr) node = root; 
  if (root == nullptr) return false; 
  const bool res = Search(node, k - root->val, root); 
  if (res) return true; 
  return findTarget(root->left, k) ||  
         findTarget(root->right, k); 
} 

// 1315. Sum of Nodes with Even-Valued Grandparent 
// Method 1 
int GetGrandChildren(TreeNode* root) { 
  return (root->left?((root->left->left?root->left->left->val:0)  
       + (root->left->right?root->left->right->val:0)):0) +  
         (root->right?((root->right->left?root->right->left->val:0)  
       + (root->right->right?root->right->right->val:0)) :0); 
} 

int sumEvenGrandparent(TreeNode* root) { 
  if (root == nullptr) return 0;  
  int root_val = 0; 
  if (!(root->val & 1)) { 
    root_val = GetGrandChildren(root); 
  } 
  return root_val + sumEvenGrandparent(root->left) 
                  + sumEvenGrandparent(root->right); 
} 

// Method 2 
int sumEvenGrandparent(TreeNode* root, int p = 1, int gp = 1) { 
  return root ? sumEvenGrandparent(root->left, root->val, p) 
               + sumEvenGrandparent(root->right, root->val, p) 
               + (gp % 2 ? 0 : root->val)  : 0; 
} 

// 508. Most Frequent Subtree Sum 
unordered_map<int, int> record_;  
int FindFrequentTreeSum(TreeNode* root) { 
  if (root == nullptr) return 0;   
  int sum_left = 0; 
  int sum_right = 0; 
  if (root->left) sum_left = FindFrequentTreeSum(root->left); 
  if (root->right) sum_right = FindFrequentTreeSum(root->right); 
  int tree_sum = sum_left + sum_right + root->val; 
  ++record_[tree_sum]; 
  return tree_sum; 
} 

vector<int> findFrequentTreeSum(TreeNode* root) { 
  if (root == nullptr) return {}; 
  FindFrequentTreeSum(root); 
  int max_val = max_element( 
       record_.begin(), record_.end(), [](const auto& p1, const auto& p2) { 
       return p1.second < p2.second; 
  })->second; 
  vector<int> max_sums; 
  for_each(record_.begin(), record_.end(),  
               [&max_sums, max_val](const auto& p1) { 
    if (p1.second == max_val) max_sums.push_back(p1.first); 
  }); 
  return max_sums; 
}  

// 666. Path Sum IV 
int ttl_sum_ = 0; 
void GetSum(int val, unordered_map<int, int>& record, int cur_sum) { 
  if (record.find(val) == record.end()) return; 
  int left_key = 10*(val/10 + 1) + (((val%10)-1) << 1) + 1; 
  int right_key = left_key + 1; 
  if (record.find(left_key) == record.end() &&  
      record.find(right_key) == record.end()) { 
    ttl_sum_ += record[val] + cur_sum; 
    return; 
  } 
  GetSum(left_key, record, record[val] + cur_sum);  
  GetSum(right_key, record, record[val] + cur_sum); 
} 

int pathSum(vector<int>& nums) { 
  unordered_map<int, int> record_; 
  for (const auto num : nums) record_[num/10] = num % 10; 
  GetSum(11, record_, 0); 
  return ttl_sum_; 
} 

// 124. Binary Tree Maximum Path Sum 
// One return for current root maximum, the other maintains the cur_max_sum 
int MaxPathSum(TreeNode* root, int& max_sum) { 
  if (root == nullptr) return 0; 
  int left_sum = max(MaxPathSum(root->left, max_sum), 0); 
  int right_sum = max(MaxPathSum(root->right, max_sum), 0); 
  int root_val = root->val; 
  max_sum = max(root_val + left_sum + right_sum, max_sum); 
  return max(root_val + left_sum, root_val + right_sum); 
}   

int maxPathSum(TreeNode* root) { 
  int max_sum = INT_MIN; 
  if (root != nullptr)  
    MaxPathSum(root, max_sum); 
  return max_sum; 
} 

// 236. Lowest Common Ancestor of a Binary Tree 
TreeNode* lowestCommonAncestor(TreeNode* root,  
                               TreeNode* p, TreeNode* q) { 
  if (root == nullptr || root == p || root == q) return root; 
  TreeNode* left_res = lowestCommonAncestor(root->left, p, q); 
  TreeNode* right_res = lowestCommonAncestor(root->right, p, q); 
  return left_res == nullptr?right_res: 
         (right_res == nullptr?left_res:root); 
} 

// 235. Lowest Common Ancestor of a Binary Search Tree 
TreeNode* lowestCommonAncestor(TreeNode* root,  
                               TreeNode* p, TreeNode* q) { 
  TreeNode* cur = root; 
  const auto p_val = p->val; 
  const auto q_val = q->val; 
  while (cur != nullptr) { 
    const auto cur_val = cur->val; 
    if (cur_val < p_val && cur_val < q_val) cur = cur->right; 
    else if (cur_val > p_val && cur_val > q_val) cur = cur->left; 
    else return cur; 
  } 
  return cur; 
} 

// 1257. Smallest Common Region 
string findSmallestRegion(vector<vector<string>>& regions, string region1, string region2) { 
  unordered_map<string, string> records; 
  for (const auto record : regions) { 
    for (int idx = record.size() - 1; idx > 0; --idx) { 
      records[record[idx]] =record[0]; 
    } 
  } 
  unordered_set<string> path; 
  path.insert(region1); 
  while (records.find(region1) != records.end()) { 
    path.insert(records[region1]); 
    region1 = records[region1]; 
  } 
  if (path.find(region2) != path.end()) return region2; 
  while (records.find(region2) != records.end()) { 
    if (path.find(records[region2]) != path.end()) return records[region2]; 
    region2 = records[region2]; 
  } 
  return ""; 
} 

// 173. Binary Search Tree Iterator 
// Inorder non-recursive method 
stack<TreeNode*> record; 
BSTIterator(TreeNode* root) { 
  while (root != nullptr)  { 
    record.push(root); 
    root = root->left; 
  }       
} 

/** @return the next smallest number */ 
int next() { 
  const auto tpr = record.top(); 
  const int tpr_val = tpr->val; 
  record.pop(); 
  auto tpr_right = tpr->right; 
  while (tpr_right != nullptr) { 
    record.push(tpr_right); 
    tpr_right = tpr_right->left; 
  } 
  return tpr_val; 
} 

/** @return whether we have a next smallest number */ 
bool hasNext() { 
  return record.size() > 0;     
}  

// 1123. Lowest Common Ancestor of Deepest Leaves
unordered_map<TreeNode*, int> depth_record_;
TreeNode* lcaDeepestLeaves(TreeNode* root) {
  if (root == nullptr) return nullptr;
  int left_depth = CountMaxDepth(root->left);
  int right_depth = CountMaxDepth(root->right);
  if (left_depth > right_depth) return lcaDeepestLeaves(root->left);
  else if (left_depth < right_depth) return lcaDeepestLeaves(root->right);
  else return root;
}
  
int CountMaxDepth(TreeNode* root) {
  if (root == nullptr) return 0;
  if (depth_record_.count(root) > 0) return depth_record_[root];
  depth_record_[root] = 1 + max(CountMaxDepth(root->left), 
                                CountMaxDepth(root->right));
  return depth_record_[root];
}

// 834. Sum of Distances in Tree -> More like a graph problem.