代码随想录一刷笔记_二叉树（下）

60+在408的算法考察难度和深度上还是收手了👍）

二叉树的最近公共祖先（236）&二叉搜索树的最近公共祖先（235）

No.236

思路：双层遍历二叉树，找到公共节点。

使用递归的方法的话，是从叶子节点向上遍历二叉树的（回溯的思想），所以在找到的第一个公共子节点就是最近的公共祖先，直接返回即可。

也就是说，类比一下，如果使用迭代的方法，就可以找到最远的公共祖先。

No.235

由于BSP树具有按序排列的特征，所以相比No.236，这题显得简单很多，只要往下寻找处于两个节点中间的层数最深的节点即可。

tips：根据递归的三部曲，第二部（确定终止条件）按照题目叙述可以直接省略。题目中说了p、q 为不同节点且均存在于给定的二叉搜索树中。也就是说一定会找到公共祖先的，所以并不存在遇到空的情况

删除二叉搜索树中的节点（450）

删除节点的操作可以简单分为两步：分别是找到并删除这个节点（题解里是利用了BSP树中数值按顺序排序的特点来查找节点的），然后是调整二叉树的结构。

关于如何调整二叉树，可以分为4种情况：

1. 要删除的节点不存在（有点搞笑）

2. 要删除的节点没有子树 -> 直接删除节点

3. 要删除的节点只有一边有子树 -> 子树替代被删除节点的位置

4. 要删除的节点包含左右子树 -> 选择的处理方法：右子树替代被删除节点，左子树节点挪至右子树的最左节点。

   一开始，

在厘清整个环节后，整个算法的实现对我来说最难的是找到这个节点及其父节点(っ °Д °;)っ（分别使用了两个函数找该节点和父节点，但是最后用时分布竟然击败100%，不可思议！）。

经过询问gpt，能够用pair这个数据结构直接返回两个节点，nb！

pair<TreeNode *, TreeNode*> travelsal(TreeNode *node, TreeNode *parent, int key) 
{
    if (!node) return {nullptr, nullptr};

    if (node->val == key) return {node, parent};

    auto left = travelsal(node->left, node, key);
    if (left.first) return left;

    auto right =  travelsal(node->right, node, key);
    if (right.first) return right;

    return {nullptr, nullptr};
}

在有返回值的情况下，写递归函数有两点需要注意：

1. 得声明一个节点取到递归函数返回的值，然后再对其进行判断；
2. 函数的最后有一个返回值，避免极端的情况发生。

感觉在涉及使用递归方法查找二叉树的节点时，写的代码都不够漂亮，还得多写写。

修剪二叉搜索树（669）

思路：这一题的主线是遍历二叉树，当找到不符合要求的节点时对其进行删除操作，然后从当前节点继续遍历下去。

针对上面的思路，我的评价是我又把他当成普通二叉树来做了！！！！

这一题只要按照中序遍历找到截断点断掉就行，我趣！！

通过返回值移除节点

遇到需要删除的节点时，将这个节点的子节点作为返回值向上返回，回溯上去后，被删除节点进行接收的操作👍。

TreeNode* trimBST(TreeNode* root, int low, int high) {
     if (!root) return nullptr;

     if (root->val < low) return trimBST(root->right, low, high);
     if (root->val > high) return trimBST(root->left, low, high);

     root->left = trimBST(root->left, low, high);
     root->right = trimBST(root->right, low, high);

     return root;
}

将有序数组转换为二叉搜索树（108）

构造二叉树的思路是：找到节点对应的数值，把现有的数组分割为左右子树对应的两堆，并进行迭代。使用递归的写法会方便很多。

PS: 需要注意边界条件！

把二叉搜索树转换为累加树（1038）

这题就是按照右中左的顺序遍历二叉树，然后累加遇到节点的值。

fin.