【算法篇】二叉树类（3）（笔记）

目录

一、Leetcode 题目

1. 二叉树的最近公共祖先

2. 二叉搜索树的最近公共祖先

（1）递归法

（2）迭代法

3. 二叉搜索树中的插入操作

（1）递归法

（2）迭代法

4. 删除二叉搜索树中的节点

（1）递归法

（2）迭代法

5. 修剪二叉搜索树

（1）递归法

（2）迭代法

6. 将有序数组转换为二叉搜索树

7. 把二叉搜索树转换为累加树

（1）迭代法

（2）递归法

二、二叉树类题目录友总结

---

一、Leetcode 题目

1. 二叉树的最近公共祖先

236. 二叉树的最近公共祖先 - 力扣（LeetCode）https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/

        给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

        百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 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 。因为根据定义最近公共祖先节点可以为节点本身。示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1

思路：

        遇到空的话，因为树都是空了，所以返回空。

        那么我们来说一说，如果 root == q，或者 root == p，说明找到 q p ，则将其返回，这个返回值，后面在中节点的处理过程中会用到

        在递归函数有返回值的情况下：如果要搜索一条边，递归函数返回值不为空的时候，立刻返回，如果搜索整个树，直接用一个变量 left、right 接住返回值，这个 left、right 后序还有逻辑处理的需要，也就是后序遍历中处理中间节点的逻辑（也是回溯）。

        就像图中一样直接返回 7。

        如果 left 和 right 都不为空，说明此时 root 就是最近公共节点。这个比较好理解

        如果 left为空，right 不为空，就返回 right，说明目标节点是通过 right 返回的，反之依然。

        图中节点 10 的左子树返回 null，右子树返回目标值 7，那么此时节点 10 的处理逻辑就是把右子树的返回值（最近 公共祖先 7）返回上去！

        完整流程图如下：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {// 后序遍历// 如果找到节点了，就将节点返回。返回为 NULL 的话表示为没有找到题目给出的节点if (root == p || root == q || root == NULL) return root;// 左右节点递归，以得到每一层的回溯结果TreeNode* left = lowestCommonAncestor(root->left, p, q);TreeNode* right = lowestCommonAncestor(root->right, p, q);// 判断回溯到上一层什么节点if (left != NULL && right != NULL) return root;   // 左右节点都有返回值，表示为给出的节点在 root 节点的左右子树上。不是 NULL，表示现在的 root 是他们的根节点// 更新着返回 root，直到返回的 root 不变，表示为已找到 最近的祖先 else if (left == NULL && right != NULL) return right;// 这里返回 right，表示为给出的节点在都在 右子树上// 返回 left，表示为给出的节点在都在 左子树上return left;}
};

2. 二叉搜索树的最近公共祖先

235. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/description/

        给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

        百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

        例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

思路：

        因为是有序树，所以 如果 中间节点是 q 和 p 的公共祖先，那么 中节点的数组 一定是在 [p, q]区间的。即 中节点 > p && 中节点 < q 或者 中节点 > q && 中节点 < p。

        当我们从 上向下去递归遍历，第一次遇到 cur 节点是数值在 [q, p] 区间中，那么 cur 就是 q 和 p 的最近公共祖先。

（1）递归法

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/// 写法一：
class Solution {
public:TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q) {if (cur == NULL) return cur;if (cur->val > p->val && cur->val > q->val) {TreeNode* left = traversal(cur->left, p, q);if (left != NULL) {return left;}}if (cur->val < p->val && cur->val < q->val) {TreeNode* right = traversal(cur->right, p, q);if (right != NULL) {return right;}}return cur;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {return traversal(root, p, q);}
};// 写法二
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root->val > p->val && root->val > q->val) {return lowestCommonAncestor(root->left, p, q);}else if (root->val < p->val && root->val < q->val) {return lowestCommonAncestor(root->right, p, q);}else return root;}
};

（2）迭代法

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {while(root) {if (root->val > p->val && root->val > q->val) {root = root->left;} else if (root->val < p->val && root->val < q->val) {root = root->right;} else return root;}return NULL;}
};

3. 二叉搜索树中的插入操作

701. 二叉搜索树中的插入操作 - 力扣（LeetCode）https://leetcode.cn/problems/insert-into-a-binary-search-tree/description/

        给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

        注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

示例 1：
输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]
解释：另一个满足题目要求可以通过的树是：

示例 2：
输入：root = [40,20,60,10,30,50,70], val = 25
输出：[40,20,60,10,30,50,70,null,null,25]示例 3：
输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
输出：[4,2,7,1,3,5]

（1）递归法

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* parent;void traversal(TreeNode* cur, int val) {if (cur == nullptr) {TreeNode* node = new TreeNode(val);if (val < parent->val) parent->left = node;else parent->right = node;return;}parent = cur;if (val < cur->val) traversal(cur->left, val);if (val > cur->val) traversal(cur->right, val);return;}TreeNode* insertIntoBST(TreeNode* root, int val) {if (root == nullptr) {TreeNode* node = new TreeNode(val);return node;}traversal(root, val);return root;}
};

（2）迭代法

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* insertIntoBST(TreeNode* root, int val) {if (root == nullptr) {TreeNode* node = new TreeNode(val);return node;}TreeNode* cur = root;TreeNode* parent = cur;// 找到对应的节点进行插入while (cur != nullptr) {parent = cur;if (val < cur->val) cur = cur->left;else cur = cur->right;}// 底层插入元素TreeNode* node = new TreeNode(val);if (val < parent->val) parent->left = node;else parent->right = node;return root;}
};

4. 删除二叉搜索树中的节点

450. 删除二叉搜索树中的节点 - 力扣（LeetCode）https://leetcode.cn/problems/delete-node-in-a-bst/description/

        给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

        一般来说，删除节点可分为两个步骤：

1. 首先找到需要删除的节点；
2. 如果找到了，删除它。

示例 1:
输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。

示例 2:
输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点示例 3:
输入: root = [], key = 0
输出: []

思路：

        递归：单层递归的逻辑，有五种情况：

• 第一种情况：没找到删除的节点，遍历到空节点直接返回了
• 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
• 第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
• 第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
• 第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。

（1）递归法

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {if (root == nullptr) return root; // 第一种情况：没找到删除的节点，遍历到空节点直接返回了if (root->val == key) {// 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点if (root->left == nullptr && root->right == nullptr) {delete root;return nullptr;}// 第三种情况：其左孩子为空，右孩子不为空，删除节点，右孩子补位 ，返回右孩子为根节点else if (root->left == nullptr) {auto retNode = root->right;delete root;return retNode;}// 第四种情况：其右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点else if (root->right == nullptr) {auto retNode = root->left;delete root;return retNode;}// 第五种情况：左右孩子节点都不为空，则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置// 并返回删除节点右孩子为新的根节点。else {TreeNode* cur = root->right; // 找右子树最左面的节点while(cur->left != nullptr) {cur = cur->left;}cur->left = root->left; // 把要删除的节点（root）左子树放在cur的左孩子的位置TreeNode* tmp = root;   // 把root节点保存一下，下面来删除root = root->right;     // 返回旧root的右孩子作为新rootdelete tmp;             // 释放节点内存（这里不写也可以，但C++最好手动释放一下吧）return root;    // 交给上一层递归指向新 root}}if (root->val > key) root->left = deleteNode(root->left, key);if (root->val < key) root->right = deleteNode(root->right, key);return root;}
};

（2）迭代法

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* deleteOneNode(TreeNode* cur) {if (cur == nullptr) return cur;if (cur->right == nullptr) return cur->left;// 两边都不为空TreeNode* target = cur->right;while (target->left) {target = target->left;}target->left = cur->left;return cur->right;}TreeNode* deleteNode(TreeNode* root, int key) {if (root == nullptr) return nullptr;TreeNode* cur = root;TreeNode* pre = nullptr;while (cur) {if (cur->val == key) break;pre = cur;if (key < cur->val) cur = cur->left;else cur = cur->right;}// 没找到节点if (pre == nullptr) { // 如果搜索树只有头结点return deleteOneNode(cur);}// 找到了需要判断if (pre->left && pre->left->val == key) {pre->left = deleteOneNode(cur);}if (pre->right && pre->right->val == key) {pre->right = deleteOneNode(cur);}return root;}
};

5. 修剪二叉搜索树

669. 修剪二叉搜索树 - 力扣（LeetCode）https://leetcode.cn/problems/trim-a-binary-search-tree/description/

        给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。

        所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

示例 1：
输入：root = [1,0,2], low = 1, high = 2
输出：[1,null,2]

示例 2：
输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出：[3,2,null,1]

（1）递归法

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {if (root == nullptr) 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;}
};

（2）迭代法

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {// 迭代法if (root == nullptr) return root;// 取一个范围，一定有一个搜索二叉树中的根节点在范围中间，而且左右子树都需要修剪// 首先找到这个根节点while (root != nullptr && (root->val < low || root->val > high)) {if (root->val < low) root = root->right;else if (root->val > high) root = root->left;}TreeNode* cur = root;// 处理左节点while (cur != nullptr) {while (cur->left && cur->left->val < low) {cur->left = cur->left->right;}cur = cur->left;    // 查找左子树，直到最小值}// 处理右节点cur = root;while (cur != nullptr) {while (cur->right && cur->right->val > high) {cur->right = cur->right->left;}cur = cur->right;    // 查找右子树，直到最大值}return root;}
};

6. 将有序数组转换为二叉搜索树

108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/

        给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

示例 1：
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：
输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/// 递归法
class Solution {
public:TreeNode* buildTree(vector<int>& nums, int left, int right) {   // [):左闭右开if (left == right) return nullptr;// 获取根节点int mid = (left + right) / 2;// int mid = left + ((right - left) / 2);TreeNode* root = new TreeNode(nums[mid]);root->left = buildTree(nums, left, mid);root->right = buildTree(nums, mid + 1, right);return root;}TreeNode* sortedArrayToBST(vector<int>& nums) {return buildTree(nums, 0, nums.size());}
};

7. 把二叉搜索树转换为累加树

538. 把二叉搜索树转换为累加树 - 力扣（LeetCode）https://leetcode.cn/problems/convert-bst-to-greater-tree/description/

        给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

• 节点的左子树仅包含键 小于 节点键的节点。
• 节点的右子树仅包含键 大于 节点键的节点。
• 左右子树也必须是二叉搜索树。

示例 1：
输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]示例 2：
输入：root = [0,null,1]
输出：[1,null,1]示例 3：
输入：root = [1,0,2]
输出：[3,3,2]示例 4：
输入：root = [3,2,4,1]
输出：[7,9,4,10]

（1）迭代法

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* convertBST(TreeNode* root) {// 反中序遍历stack<TreeNode*> record;if (root == nullptr) return root;record.push(root);int sum = INT_MAX;while (!record.empty()) {TreeNode* node = record.top();record.pop();if (node != nullptr) {if (node->left) record.push(node->left);record.push(node);record.push(nullptr);if (node->right) record.push(node->right);}else {node = record.top();record.pop();if (sum == INT_MAX) {// 初始化 sumsum = node->val;}else {sum += node->val;node->val = sum;}}}return root;}
};

（2）递归法

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
private:int pre = 0; // 记录前一个节点的数值void traversal(TreeNode* cur) { // 右中左遍历if (cur == NULL) return;traversal(cur->right);cur->val += pre;pre = cur->val;traversal(cur->left);}
public:TreeNode* convertBST(TreeNode* root) {pre = 0;traversal(root);return root;}
};

二、二叉树类题目录友总结