• LeetCode 236. 二叉树的最近公共祖先(C++)

    题目地址：力扣

    假设我们的根节点是root，要找的两个节点分别为p和q。从题目给的例子中可以分析最近公共祖先的两种情况：

    1、当前节点既不是p也不是q，但是其左子树和右子树分别包含着p和q，那么当前节点就是p和q的最近公共祖先

    2、当前节点可能是p或者q的一个，而其左子树或者右子树包含着p或q的另一个，那么当前节点就应该是p和q的最近公共祖先

    由于我们判断的是左子树或右子树是否包含p或q，因此在第一种情况并非一定要祖先的左右节点正好是p,q，而是祖先的左子树中包含p，右子树中包含q即可。因此这里就涉及到状态传递，也就是只要左子树中某个节点是p，那么我们就要将这个信息传给其父节点，并一直往上传。由于我们需要先判断左子树和右子树的情况，再往上传，因此很自然就想到了左->右->根的遍历思路，所以我们需要采用后序遍历。而子树是否包含p或q，我们可以用一个布尔值来进行判断。

    解法1：后序遍历递归

    1. class Solution {
    2. public:
    3.     bool postOrder(TreeNode* root, TreeNode* p, TreeNode* q) {
    4.         // 首先初始化当前节点的状态为false，代表当前节点既不是p也不是q
    5.         bool curflag = false;
    6.         // 若根节点非空
    7.         if (root != nullptr) {
    8.             // 若根节点是p或者根节点是q的话，将状态置为true
    9.             if (root == p || root == q)
    10.                 curflag = 1;
    11.             // 递归遍历左子树和右子树
    12.             bool lflag = postOrder(root->left, p, q);
    13.             bool rflag = postOrder(root->right, p, q);
    14.             // 若左子树和右子树其中有一者是p或q
    15.             if (lflag || rflag ) {
    16.                 // 若当前节点是p或q，说明对应第二种情况，即最近祖先就是当前节点
    17.                 if (curflag) {
    18.                     resptr = root;
    19.                 // 若当前节点不是p也不是q，判断是否左右子树二者分别包含p,q
    20.                 } else {
    21.                     // 对应第一种情况，当前节点不是，但左右子树是，最近祖先就是当前节点
    22.                     if (lflag && rflag )
    23.                         resptr = root;
    24.                 }
    25.                 // 由于左右子树至少一者是，因此将状态传递给当前节点
    26.                 curflag = true;
    27.             }
    28.         }
    29.         return curflag;
    30.     }
    31.  
    32.     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    33.         // 后序遍历
    34.         postOrder(root, p, q);
    35.         return resptr;
    36.     }
    37. private:
    38.     // 用于存储最近祖先节点的指针
    39.     TreeNode* resptr;
    40. };

    解法2：后序遍历递归（提前终止）

    思路：我们换一个角度来看这个问题，由于题目中说p和q一定是两个存在的且在树中的节点。假设我们从root开始找，而且我们只关注与root与它的左右孩子。

    • 假设其左孩子是p，右孩子是空，那么说明q一定在其左孩子的子树里面，因此p一定是q的祖先，p也是二者的最近祖先
    • 假设其左孩子是p，右孩子是q，那么说明当前节点一定是p和q的最近祖先

    其核心思想就是，对于某个节点（假设为curNode）来说，假设我找到了一个左孩子或者右孩子是p或者q，那么我就不需要继续往下递归找我的子树了，我只需要往上返回这个节点（假设为findNode）即可，让上层节点（curNode的父节点）判断它的右子树情况，若上层节点的右子树没找到p或者q，说明剩下一个一定在findNode的子树里面。若上层节点的右子树找到了p或者q，说明上层节点就是最近祖先。

    因此，我们递归的时候只要找到了p或者q的一者，那么最近祖先要么就是当前找到的这一者，要么就是这一者的父节点，没有例外。具体是这一者还是其父节点，要交给其父节点来判断。

    1. class Solution {
    2. public:
    3.     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    4.         // 碰到这三种情况返回，要么空，要么是p，要么是q，否则继续递归
    5.         if (!root || root == p || root == q) 
    6.             return root;
    7.         
    8.         TreeNode *left = lowestCommonAncestor(root->left, p, q);
    9.         TreeNode *right = lowestCommonAncestor(root->right, p, q);
    10.         // 交给父节点来判断，若左右子树分别包含了p和q，那么父节点就是最近祖先
    11.         if (left && right) 
    12.             return root;
    13.         // 若左右子树一者包含p或q，那么就祖先节点就是那一者
    14.         return left ? left : right;
    15.     }
    16. };

    解法3：反向构树

    思路：既然要求公共最近祖先，而p和q是树中的某一个节点。我只要p和q都往根节点走，那么他们一定会在某个节点相遇或者从某个节点开始走同一条路。但是树的结构又不支持往根节点走，因此我们可以通过遍历树，存下每个节点的父节点，相当于反向构建一棵树。这样我们就可以使用这个方法了。

    1. class Solution {
    2. public:
    3.     // 先序遍历
    4.     void preOrder(TreeNode* root, unordered_map &fa_map)
    5.     {
    6.         if (root != nullptr)
    7.         {
    8.             if (root->left != nullptr)
    9.                 fa_map[root->left] = root;
    10.             if (root->right != nullptr)
    11.                 fa_map[root->right] = root;
    12.             preOrder(root->left, fa_map);
    13.             preOrder(root->right, fa_map);
    14.         }
    15.     }
    16.  
    17.     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    18.         // fa_map用于存储父节点，node_set用于存储找根的时候经历的节点
    19.         unordered_map fa_map;
    20.         unordered_set node_set;
    21.         // 定义res节点用于返回
    22.         TreeNode *res = nullptr;
    23.         // 构建反向树
    24.         fa_map[root] = nullptr;
    25.         preOrder(root, fa_map);
    26.         // 先从p找到根，把经历的节点加入node_set
    27.         while (p != nullptr)    
    28.         {
    29.             node_set.insert(p);
    30.             p = fa_map[p];
    31.         }
    32.         // 从q往根找，只要碰到了经历过的节点，那么这个节点就是最近祖先
    33.         while(q != nullptr)
    34.         {
    35.             if (node_set.find(q) != node_set.end()) {
    36.                 res = q;
    37.                 break;
    38.             }
    39.             q = fa_map[q];
    40.         }
    41.         return res;
    42.     }
    43. };

    Accepted

    • 31/31 cases passed (12 ms)
    • Your runtime beats 93.61 % of cpp submissions
    • Your memory usage beats 69.52 % of cpp submissions (13.8 MB)

  • 相关阅读:
    1615. 最大网络秩
    搭建花店小程序商城的详细步骤
    18. 注入 Servlet、Filter、Listener
    RDD算子介绍
    从功能测试到自动化测试，待遇翻倍的秘籍在这里~
    实现让一个字符串在命令行同一行滑动
    windows环境下tensorflow安装
    lombok ---- pojo简洁之道
    GO微服务实战第三十节 OpenTracing 规范介绍与分布式链路追踪组件选型
    深度强化学习之gym扫地机器人环境的搭建(持续更新算法，附源码，python实现）
  • 原文地址：https://blog.csdn.net/Xavier_97/article/details/126851358