【Leetcode笔记】236.二叉树的最近公共祖先

本文主要是介绍【Leetcode笔记】236.二叉树的最近公共祖先，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目要求

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

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

ACM

本题适合从下往上遍历，所以使用后序遍历来递归。

#include <iostream>
#include <vector>
using namespace std;
// #include <unordered_map>
// #include <algorithm>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) {}
};class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root == p || root == q || root == NULL){return root;}    //左TreeNode* left = lowestCommonAncestor(root->left, p, q);//右TreeNode* right = lowestCommonAncestor(root->right, p, q);//根if(left == NULL) return right;if(right == NULL) return left;return root;}
};int main(void)
{TreeNode* root = new TreeNode(8);root->left = new TreeNode(10);root->right = new TreeNode(4);root->left->left = new TreeNode(1);root->left->right = new TreeNode(7);root->right->left = new TreeNode(15);root->right->right = new TreeNode(20);root->left->right->left = new TreeNode(6);root->left->right->right = new TreeNode(5);Solution solution;TreeNode* p = root->left->right->left;TreeNode* q = root->left->right->right;TreeNode* result = solution.lowestCommonAncestor(root, p, q);cout << "Lowest Common Ancestor: " << result->val << endl;return 0;   
}

测试代码中 p、q 的定义，不能简单地定义一个根节点，TreeNode* p = new TreeNode(6);

TreeNode* p = new TreeNode(5);

运行结果

这篇关于【Leetcode笔记】236.二叉树的最近公共祖先的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---