程序员代码面试指南 3.18：在二叉树中找两节点最近公共祖先

1、思路

• 对二叉树进行前序遍历，找到目标节点后就返回该节点；

• 每次递归分三种情况讨论：

  1、若当前节点的左右子树返回值都不为空，则当前节点即是最近公共祖先；

  2、若只有左子树返回值不为空，说明其中一个节点或者两个节点都在左子树，直接返回左子树的返回值；

  3、若只有右子树返回值不为空，同上。

2、代码

#include <iostream>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left, *right;

    TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {}
};

void createTree(TreeNode *root)                             //建树
{
    int rootVal, leftVal, rightVal;
    cin >> rootVal >> leftVal >> rightVal;

    if (leftVal != 0)
    {
        root->left = new TreeNode(leftVal);
        createTree(root->left);
    }

    if (rightVal != 0)
    {
        root->right = new TreeNode(rightVal);
        createTree(root->right);
    }
}

TreeNode* lowestAncestor(TreeNode *root, int p, int q)
{
    if (root == nullptr) return nullptr;

    if (root->val == p || root->val == q) return root;

    TreeNode *left = lowestAncestor(root->left, p, q);
    TreeNode *right = lowestAncestor(root->right, p, q);

    if (left != nullptr && right != nullptr) return root;   //三种情况
    else if (left != nullptr) return left;
    else return right;
}

int main()
{
    int n, rootVal;
    cin >> n >> rootVal;

    TreeNode *root = new TreeNode(rootVal);
    createTree(root);

    int p, q;
    cin >> p >> q;

    cout << lowestAncestor(root, p, q)->val << endl;

    return 0;
}