leetcode236：二叉树的最近公共祖先

题目链接

leetcode

题目描述

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为：”对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。“

C++ 代码

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>
#include <algorithm>
using namespace std;

// 二叉树结点的定义
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

const int NULL_NODE = -1e9 - 1;

// 辅助函数：创建二叉树
TreeNode* createTree(const vector<int>& nums) {
    if (nums.empty()) return nullptr;

    TreeNode* root = new TreeNode(nums[0]);
    queue<TreeNode*> queue;
    queue.push(root);
    int i = 1;
    while (!queue.empty() && i < nums.size()) {
        TreeNode* node = queue.front(); queue.pop();
        if (nums[i] != NULL_NODE) {
            node->left = new TreeNode(nums[i]);
            queue.push(node->left);
        }
        i++;
        if (i < nums.size() && nums[i] != NULL_NODE) {
            node->right = new TreeNode(nums[i]);
            queue.push(node->right);
        }
        i++;
    }

    return root;
}

// 辅助函数：层序遍历打印二叉树
void levelOrderTraversal(TreeNode* root) {
    if (root == nullptr) return;

    queue<TreeNode*> queue;
    queue.push(root);
    while (!queue.empty()) {
        TreeNode* node = queue.front(); queue.pop();
        cout << node->val << " ";
        if (node->left != nullptr) queue.push(node->left);
        if (node->right != nullptr) queue.push(node->right);
    }
    cout << endl;
}

// 辅助函数：释放二叉树
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

/*
    递归实现

    递归函数的定义：该函数输入三个参数 root，p，q，它会返回一个结点。
    根据这个定义，分情况讨论：
        若 p 和 q 都不在以 root 为根的树中，则返回 null。
        若 p 和 q 都在以 root 为根的树中，则 left 和 right 一定分别是 p 和 q。
        若 p 和 q 只有一个在以 root 为根的树中，则返回该结点。
    
    时间复杂度：O(n)
        其中 n 是二叉树的结点数。
        二叉树的所有结点只会被访问一次，因此时间复杂度为 O(n)。
    空间复杂度：O(n)
        递归调用的栈深度取决于二叉树的高度，
        最坏情况下为一条链，此时高度为 n，因此空间复杂度为 O(n)。
*/
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr || root == p || root == q) {
            return root;
        }

        // 递归处理左子树和右子树
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);

        if (left != nullptr && right != nullptr) {
            return root;
        }
        if (left == nullptr && right == nullptr) {
            return nullptr;
        }
        return left != nullptr ? left : right;
    }
};

/*
    递归实现，存储父节点

    1.从根结点开始遍历整棵二叉树，用哈希表 parent 记录每个结点的父结点指针。
    2.从 p 结点开始不断往它的祖先移动，用哈希表 visited 记录已经访问过的祖先结点。   
    3.再从 q 结点开始不断往它的祖先移动。
    若祖先已经被访问过，则这是 p 和 q 最深的公共祖先，即 LCA 结点。

    时间复杂度：O(n)
    空间复杂度：O(n)
*/
class Solution_2 {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        parent[root->val] = nullptr;
        dfs(root);

        while (p != nullptr) {
            visited[p->val] = true;
            p = parent[p->val];
        }
        while (q != nullptr) {
            if (visited[q->val]) return q;
            q = parent[q->val];
        }
        
        return nullptr;
    }

    void dfs(TreeNode* root) {
        if (root->left != nullptr) {
            parent[root->left->val] = root;
            dfs(root->left);
        }
        if (root->right != nullptr) {
            parent[root->right->val] = root;
            dfs(root->right);
        }
    }

private:
    unordered_map<int, TreeNode*> parent;
    unordered_map<int, bool> visited;
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

// 辅助函数：打印二维数组
void printArray(const vector<vector<int>>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << "[";
        for (size_t j = 0; j < nums[i].size(); j++) {
            cout << nums[i][j];
            if (j != nums[i].size() - 1) cout << ",";
        }
        cout << "]";
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

// 通过值查找节点
TreeNode* findNode(TreeNode* root, int val) {
    if (root == nullptr) {
        return nullptr;
    }
    if (root->val == val) {
        return root;
    }

    TreeNode* left = findNode(root->left, val);
    if (left != nullptr) {
        return left;
    }
    return findNode(root->right, val);
}

int main() {
    Solution solution;
    vector<vector<int>> root_cases = {
        {3,5,1,6,2,0,8,NULL_NODE,NULL_NODE,7,4},
        {3,5,1,6,2,0,8,NULL_NODE,NULL_NODE,7,4},
        {1,2}
    };
    vector<vector<int>> vals_cases = {
        {5, 1},
        {5, 4},
        {1, 2}
    };

    for (int i = 0; i < root_cases.size(); i++) {
        TreeNode* root = createTree(root_cases[i]);
        int p_val = vals_cases[i][0];
        int q_val = vals_cases[i][1];
        TreeNode* p = findNode(root, p_val);
        TreeNode* q = findNode(root, q_val);

        cout << "Input: ";
        printArray(root_cases[i]);
        TreeNode* result = solution.lowestCommonAncestor(root, p, q);
        cout << "Output: " << result->val << endl;

        // 释放内存
        deleteTree(root);
    }

    return 0;
}