/*
* DFS
*/
#include <iostream>
#include <vector>
using namespace std;
struct Node {
int val;
Node *left;
Node *right;
Node(int x) : val(x), left(nullptr), right(nullptr) {}
};
Node *dfs(Node *root, int p, int q) {
if (!root) return nullptr;
bool flag = false;
if (root->val == p || root->val == q) flag = true;
Node *l = dfs(root->left, p, q);
Node *r = dfs(root->right, p, q);
// 作为祖先节点
// 左右子树各自存在p,q
if (l && r) return root;
// 左子树存在,本节点存在
if (l && flag) return root;
// 右子树存在,本节点存在
if (r && flag) return root;
// 不是祖先节点,但是含有p或者q
if (flag) return root;
if (!flag && l) return l;
if (!flag && r) return r;
return nullptr;
}
Node *nearestCommonAncestor(Node *root, int p, int q) {
return dfs(root, p, q);
}
Node *buildTree(vector<int> &nums) {
// 为非空节点分配内存
int n = nums.size();
vector<Node *> nodes(n);
for (int i = 0; i < n; i++) {
if (nums[i] != INT_MAX) nodes[i] = new Node(nums[i]);
}
// 为非空节点关联左右节点
for (int i = 0; i < n; i++) {
if (nodes[i]) {
if (2 * i + 1 < n) nodes[i]->left = nodes[2 * i + 1];
if (2 * i + 2 < n) nodes[i]->right = nodes[2 * i + 2];
}
}
return nodes[0];
}
int main() {
// 建立二叉树
vector<int> nums{3, 5, 1, 6, 2, 0, 8, INT_MAX, INT_MAX, 7, 4};
Node *root = buildTree(nums);
int p = 5, q = 4;
Node *res = nearestCommonAncestor(root, p, q);
// 打印祖先节点
if (res)
cout << res->val << endl;
return 0;
}