原题地址（简单）

方法1—哈希表存储每个结点的父节点

思路

  • 用一张哈希表存储每个结点的父节点，具体方法是递归遍历整棵树来填充哈希表；
  • 再根据哈希表算出两个结点 p q 到根节点的距离，假定为 p_len q_len
  • 算出两者距离的差值 pre_len ，让远的那个先向上走 pre_len步
  • 然后再一起向上走，直到相遇。

代码

  1. class Solution {
  2. public:
  3.     unordered_map<TreeNode*, TreeNode*> parents;
  4.     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
  5.         //先从两节点向上遍历至根节点，记下步数，再让步数大的那个先走，然后再同时走。
  6.         //定义哈希表存储每个节点的父节点
  7.         parents[root] = nullptr;
  8.         setParents(root);
  9.         int p_steps = calStep(p);
  10.         int q_steps = calStep(q);
  11.         int pre_steps = p_steps - q_steps;
  12.         while(pre_steps > 0) {
  13.             p = parents[p];
  14.             pre_steps--;    
  15.         }
  16.         while(pre_steps < 0) {
  17.             q = parents[q];
  18.             pre_steps++;
  19.         }
  20.         while(1) {
  21.             if(p == q)  break;
  22.             p = parents[p];
  23.             q = parents[q];
  24.         }
  25.         return p;
  26.     }
  28.     void setParents(TreeNode* root) {
  29.         if(!root) return;
  31.         if(root->left){
  32.             parents[root->left] = root;
  33.             setParents(root->left);
  34.         }
  35.         if(root->right){
  36.             parents[root->right] = root;
  37.             setParents(root->right);
  38.         }
  39.     }
  41.     int calStep(TreeNode* t) {
  42.         int ans = 0;
  43.         while(parents[t]) {
  44.             ans++;
  45.             t = parents[t];
  46.         }
  47.         return ans;
  48.     }
  49. };

方法二—vector存储两结点的路径

这个方法要比第一个方法简单些，运行速度也更快

思路

  • 用递归遍历树，根据二叉搜索树的性质，可以很容易、很快速的得到根节点到某个结点的路径，存储在 vector 中。所以记两节点路径为 p_path q_path
  • 然后用一个循环从后向前遍历两节点的路径 vector ，直到相遇。而遍历的长度应为 min(p_path.size(), q_path.size())

代码

  1. class Solution {
  2. public:
  4.     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
  5.         vector<TreeNode*> p_path, q_path;
  6.         addPath(root, p, p_path);
  7.         addPath(root, q, q_path);
  8.         int len = min(p_path.size(), q_path.size());
  9.         int i = len - 1;
  10.         for(; i >= 0; i--) {
  11.             if(p_path[i] == q_path[i])  return p_path[i];
  12.         }
  13.         return p_path[i]; 
  14.     }
  16.     void addPath(TreeNode* root, TreeNode* t, vector<TreeNode*>& path) {
  17.         path.emplace_back(root);
  18.         if(root == t)   return;
  20.         if(root->val > t->val)  addPath(root->left, t, path);
  21.         else    addPath(root->right, t, path);
  22.     }
  23. };