day2 二叉树的最近公共祖先

不懂一点算法。

读题

给定一个二叉树，找到该树中两个指定节点的最近公共祖先；输入 root 是一个数列，表示一棵树；p 和 q 是给定的两个节点，需要找到其共同祖先。
听上去和上一题找到链表相交处很像，不过值得注意的是，树中的数字可正可负可为零，不能使用负数作为标记。
Root 和 p、q 是直接通过传参方式给定的，不需要自己写函数获取，记得以前做的都是得自己 cin 或者 scanf。还挺方便。

过程

第一思路

首先需要从输入的 root 构建树？似乎是逐行从左往右存储节点的，第 n 层有 2^(n-1) 个节点，第 n 层的第 i 个节点与第 n-1 层的第 i/2 个节点相连，向上取整。
考虑使用类似链表相交的方法做，首先从 p 节点往上爬，爬到顶端的过程中标记所有节点；接着从 q 节点往上爬，判断当前节点是否是已经标记了的节点。
于是思路为：

1. 划分层级：每层的节点数量是固定的，数列的长度是已知的，第 i 层有 2^(i-1) 个节点，求和有总共 n 层有 2^n-1 个节点；于是使用一个 while 循环递增临时变量 n，判断数列长度是否小于2^n-1；于是有 n 为层数。
2. 判断 p 和 q 分别在哪一层
   1. 首先找到 p、q 的位置（序号）
   2. 使用相同的方法找到其所处的层数 n_p 和 n_q。
3. 将 p 向上遍历并做标记。
4. 将 q 向上遍历并判断标记，记录

于是有代码：

public class Solution {

}

看了预设代码之后才发现已经是给定了 TreeNode 的结构，不需要自己操作数列。于是想要模仿之前官方题解的哈希写法，但是有一个问题是没有 parent 指针，只能向下不能向上。如果有 parent 指针，就基本和上一题是一样的；于是新建一颗带 parent 指针的树，按照之前官方题解的双指针写法。
有代码：

/**
 * Definition for p_tmp binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    struct TreeNode_new {
        int val;
        TreeNode_new *left;
        TreeNode_new *right;
        TreeNode_new *parent;
        TreeNode_new(int x) : val(x), left(NULL), right(NULL), parent(NULL) {}
    };
    // 创建新树
    TreeNode_new* cloneWithParent(TreeNode* node, TreeNode_new* parent = nullptr) {
        if (!node) return nullptr;
        TreeNode_new* newNode = new TreeNode_new(node->val);
        newNode->parent = parent;
        newNode->left = cloneWithParent(node->left, newNode);
        newNode->right = cloneWithParent(node->right, newNode);
        return newNode;
    }
    // 根据新树创建老树
    TreeNode* cloneWithoutParent(TreeNode* node) {
        if (!node) return nullptr;
        TreeNode* newNode = new TreeNode(node->val);
        newNode->left = cloneWithoutParent(node->left);
        newNode->right = cloneWithoutParent(node->right);
        return newNode;
    }
    // 寻找指定节点
    TreeNode* searchNode(TreeNode* root, int val) {
        if (!root)
            return nullptr;
        if (root->val == val)
            return root;
        TreeNode* left = searchNode(root->left, val);
        if (left)
            return left;
        return searchNode(root->right, val);
    }
    
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 创建新树
        TreeNode_new* root_new = cloneWithParent(root);
        // 新树对应的 p
        TreeNode_new* p_tmp = new TreeNode_new(p->val);
        p_tmp->left = cloneWithParent(p->left);
        p_tmp->right = cloneWithParent(p->right);
        TreeNode_new* p_ori = p_tmp;
        // 新树对应的 q
        TreeNode_new* q_tmp = new TreeNode_new(q->val);
        q_tmp->left = cloneWithParent(q->left);
        q_tmp->right = cloneWithParent(q->right);
        TreeNode_new* q_ori = q_tmp;

        while (p_tmp != q_tmp) {
            p_tmp = p_tmp ? p_tmp->parent : q_ori;
            q_tmp = q_tmp ? q_tmp->parent : p_ori;
        }
        // 找到应有的输出节点
        if(p_tmp == nullptr){
            return root;
        }else {
        TreeNode* final_out = searchNode(root, p_tmp->val);
        return final_out;
        }
    }
};

越写越复杂，结果还是错的，过不了测试；因为新的 pq 节点初始化有问题。
于是有代码：

/**
 * Definition for p_tmp binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    struct TreeNode_new {
        int val;
        TreeNode_new *left;
        TreeNode_new *right;
        TreeNode_new *parent;
        TreeNode_new(int x) : val(x), left(NULL), right(NULL), parent(NULL) {}
    };

    TreeNode_new* cloneWithParent(TreeNode* node, TreeNode_new* parent = nullptr) {
        if (!node) return nullptr;
        TreeNode_new* newNode = new TreeNode_new(node->val);
        newNode->parent = parent;
        newNode->left = cloneWithParent(node->left, newNode);
        newNode->right = cloneWithParent(node->right, newNode);
        return newNode;
    }
    
    TreeNode* cloneWithoutParent(TreeNode* node) {
        if (!node) return nullptr;
        TreeNode* newNode = new TreeNode(node->val);
        newNode->left = cloneWithoutParent(node->left);
        newNode->right = cloneWithoutParent(node->right);
        return newNode;
    }
    
    TreeNode* searchNode(TreeNode* root, int val) {
        if (!root)
            return nullptr;
        if (root->val == val)
            return root;
        TreeNode* left = searchNode(root->left, val);
        if (left)
            return left;
        return searchNode(root->right, val);
    }

    TreeNode_new* searchNode_new(TreeNode_new* root, int val) {
        if (!root)
            return nullptr;
        if (root->val == val)
            return root;
        TreeNode_new* left = searchNode_new(root->left, val);
        if (left)
            return left;
        return searchNode_new(root->right, val);
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode_new* root_new = cloneWithParent(root);

        TreeNode_new* p_tmp = searchNode_new(root_new, p->val);
        TreeNode_new* p_ori = p_tmp;

        TreeNode_new* q_tmp = searchNode_new(root_new, q->val);
        TreeNode_new* q_ori = q_tmp;

        while (p_tmp != q_tmp) {
            p_tmp = p_tmp ? p_tmp->parent : q_ori;
            q_tmp = q_tmp ? q_tmp->parent : p_ori;
        }
        if(p_tmp == nullptr){
            return root;
        }else {
            TreeNode* final_out = searchNode(root, p_tmp->val);
            return final_out;
        }
    }
};

结果

虽然代码很唐但还是通过了，执行用时 12 ms，吃了 19.29 MB 内存。

官方题解

方法一：递归

标记二叉树的每个节点子树是否包含 p 或 q；使用 dfs 遍历。如果一个节点是公共祖先，那么一定有：

1. 其子树包含 p 和 q
2. 其本身就是 p 或 q 之一，其子树包含 p 或 q 二者中的另一个。
   使用的递归方法可以说很是巧妙，执行函数时向下完成了对树的遍历搜索，return 时相当于向上回溯，执行了条件的判断。官方代码如下：

   class Solution {
   public:
       TreeNode* ans;
       bool dfs(TreeNode* root, TreeNode* p, TreeNode* q) {
           // 如果到底则返回
           if (root == nullptr) return false;
           // 向左向右搜索
           bool lson = dfs(root->left, p, q);
           bool rson = dfs(root->right, p, q);
           // 判断是否满足公共祖先的条件
           if ((lson && rson) || ((root->val == p->val || root->val == q->val) && (lson || rson))) {
               // 不断更新ans，直到最深
               ans = root;
           } 
           // 判断是否包含p、q，或者本身就是pq之一
           return lson || rson || (root->val == p->val || root->val == q->val);
       }
       TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
           dfs(root, p, q);
           return ans;
       }
   };

   非常精炼，非常优雅。

   方法二：存储父节点

   使用哈希表存储父节点。
   （其实我一开始是想要这么做的，但是不是很会使用哈希表，于是暴力克隆了一整颗树。）
   官方题解代码是：

   class Solution {
   public:
       unordered_map<int, TreeNode*> fa;
       unordered_map<int, bool> vis;
       void dfs(TreeNode* root){
           if (root->left != nullptr) {
               fa[root->left->val] = root;
               dfs(root->left);
           }
           if (root->right != nullptr) {
               fa[root->right->val] = root;
               dfs(root->right);
           }
       }
       TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
           fa[root->val] = nullptr;
           dfs(root);
           while (p != nullptr) {
               vis[p->val] = true;
               p = fa[p->val];
           }
           while (q != nullptr) {
               if (vis[q->val]) return q;
               q = fa[q->val];
           }
           return nullptr;
       }
   };

   显然同样使用了递归，dfs 遍历了一整颗树，将父节点存在了 unordered_map<int, TreeNode*> fa 中。unordered_map<int, bool> vis 是记录是否已经访问过该节点。由于 val 和节点存在一一映射关系，因此可以直接用 val 作为节点的唯一标识。

收获

已严肃学习哈希表和递归，以及树的处理方式……太优雅。
初看时，发现哈希表(unordered_map)是一一映射，似乎类似 python 中的字典？——了解后才知道二者就是同样的东西，是使用哈希表实现的数据容器。Cpp 中有有序无序两种”映射”容器，map 和unordered_map，前者是所谓红黑树，对应 python 的 sortedcontainers，后者是哈希表，对应 python 的 dict。
递归可以视作是执行分阶段的正过程与逆过程；通过递归，可以实现不能直接实现的逆过程，且写法会相当简练。