给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” 例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4] binarytree.png 示例 1: ``输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 ``输出: 3 ``解释: 节点 5 和节点 1 的最近公共祖先是节点 3。 示例 2: ``输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 ``输出: 5 ``解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。 说明:

  • 所有节点的值都是唯一的。
  • p、q 为不同节点且均存在于给定的二叉树中

解题思路

先递归遍历查找结点p和q，遍历的过程中用vector记录下他们各自经过的路径上的结点。
顺序比较p,q的vector，直到遇到val值不同，那么最后一个相同的结点即是他们的最近公共祖先
复杂度分析：递归遍历查找结点，每个结点只会被遍历一次，复杂度O(n)；分别查找两次结点，再加上一次顺序比较vector，总的时间复杂度为 O(n)+ O(n)+ O(n) = O(n)**

  1. class Solution {
  2. public:
  3.     void findNode(TreeNode* root, TreeNode* p,vector<TreeNode*>& trase,vector<TreeNode*>& res){
  4.         if(root == NULL)
  5.             return;
  7.         if(root->val == p->val){
  8.             res = trase;
  9.             return;
  10.         }
  12.         trase.push_back(root->left);
  13.         findNode(root->left,p,trase,res);
  14.         trase.pop_back();
  16.         trase.push_back(root->right);
  17.         findNode(root->right,p,trase,res);
  18.         trase.pop_back();
  19.     }
  21.     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
  22.         if(root == NULL)
  23.             return root;
  24.         vector<TreeNode*> trasep,traseq,resp,resq;
  25.         findNode(root,p,trasep,resp); 
  26.         findNode(root,q,traseq,resq); 
  27.        //将root插入到第一个位置
  28.         resp.insert(resp.begin(),root);
  29.         resq.insert(resq.begin(),root);
  30.         int i=0,j=0;
  31.         while(i<resp.size() && j < resq.size()){
  32.             if( resp[i]->val != resq[j]->val)
  33.                 break;
  34.              i++;j++;
  35.         };
  36.         return  resp[--i];
  37.     }