LeetCode 算法：二叉树的最近公共祖先 III c++-题解

解题思路：

LeetCode 上的 “二叉树的最近公共祖先 III” 题目要求解决的是在二叉树中找到两个节点的最近公共祖先（LCA）。这个问题可以通过递归的方式来解决，下面是解题的一般思路：

定义问题：给定两个值，找到二叉树中包含这两个值的最近公共祖先。

理解二叉树：二叉树是一种特殊的树形数据结构，其中每个节点最多有两个子节点。

递归方法：

递归函数将接收当前节点和两个值作为参数。

如果当前节点为空，返回空。

检查当前节点是否等于两个值中的任意一个，如果是，返回当前节点。

递归地在左子树和右子树中查找这两个值。

处理递归结果：

如果左子树和右子树都为空，说明当前节点的子树中没有找到两个值，返回空。

如果左子树和右子树都非空，说明两个值分别在左右子树中，当前节点就是它们的LCA，返回当前节点。

如果只有一个子树非空，说明两个值都在一个子树中，继续在该子树中查找LCA

c++ demo：

#include <iostream>
#include <vector>


struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 如果当前节点为空或者等于p或q，返回当前节点
        if (!root || root == p || root == q) {
            return root;
        }

        // 递归地在左子树和右子树中查找p和q
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);

        // 如果左右子树都为空，说明p和q都不在当前节点的子树中
        if (!left && !right) {
            return nullptr;
        }

        // 如果左右子树中只有一个为空，说明p和q都在非空的子树中
        if (left && !right) {
            return left;
        }
        if (!left && right) {
            return right;
        }

        // 如果左右子树都不为空，说明p在一边，q在另一边，当前节点是它们的LCA
        return root;
    }
};

int main() {
    // 构建示例二叉树
    //       2
    //      / \
    //     3   5
    //    / \   \
    //   1   4   6
    TreeNode* root = new TreeNode(2);
    root->left = new TreeNode(3);
    root->right = new TreeNode(5);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(4);
    root->right->right = new TreeNode(6);

    // 创建两个节点
    TreeNode* p = root->left->left; // 值为1的节点
    TreeNode* q = root->right->right; // 值为6的节点

    // 创建Solution对象并调用函数
    Solution solution;
    TreeNode* lca = solution.lowestCommonAncestor(root, p, q);

    // 打印结果
    if (lca) {
        std::cout << "LCA of " << p->val << " and " << q->val << " is " << lca->val << std::endl;
    }
    else {
        std::cout << "No common ancestor found." << std::endl;
    }

    // 清理内存
    delete root->left->left;
    delete root->left->right;
    delete root->right->right;
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}

输出结果：

LCA of 1 and 6 is 2

秒客网

LeetCode 算法：二叉树的最近公共祖先 III c++-题解

相关文章