爱站工具维护数码产品简约大气网站设计

​​题目来源：

        leetcode题目，网址：236. 二叉树的最近公共祖先 - 力扣（LeetCode）

解题思路：

        分别获得从根节点到两个目标节点的链路，寻找到最后一个相同节点即可。

解题代码：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {queue<TreeNode*> pLine;queue<TreeNode*> qLine;getLine(root,p,pLine);getLine(root,q,qLine);while(pLine.size()<qLine.size()){qLine.pop();}while(qLine.size()<pLine.size()){pLine.pop();}while(pLine.front()!=qLine.front()){pLine.pop();qLine.pop();}return pLine.front();}bool getLine(TreeNode* root, TreeNode* target,queue<TreeNode*>& line){if(root==nullptr){return false;}else if(root==target || getLine(root->left,target,line) || getLine(root->right,target,line)){line.push(root);return true;}return false;}
};

总结：

        官方题解给出了两种解法。第一种是递归，自底向上逐个判断该节点是否为目标节点。第二种解法是哈希表。获得 p 节点的链路后，从 q 节点开始寻找第一个在 p 的链路中的父节点。