0610刷题
LeetCode 654. 最大二叉树 LeetCode 654. 最大二叉树自己写的
直接构造左右数组：
vectorleftVec(nums.begin(),nums.begin()+weizhi); vector rightVec(nums.begin()+weizhi+1,nums.end());
整体代码如下：
class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector& nums) {
return traverse(nums);
}
TreeNode* traverse(vector& nums)
{
if(nums.size()==0) return nullptr;
int rootValue=findMax(nums).first;
TreeNode* root=new TreeNode(rootValue);
int weizhi=findMax(nums).second;
vector leftVec(nums.begin(),nums.begin()+weizhi);
vector rightVec(nums.begin()+weizhi+1,nums.end());
root->left=traverse(leftVec);
root->right=traverse(rightVec);
return root;
}
pair findMax(vector& nums)
{
int maxNum=INT_MIN;
int weizhi=INT_MIN;
for(int i=0;i
if(nums[i]>maxNum)
{
maxNum=nums[i];
weizhi=i;
}
}
return pair(maxNum,weizhi);
}
};
思路同LeetCode 106. 从中序与后序遍历序列构造二叉树
递归函数也可以直接用左右区间进行构造：
TreeNode* traversal(vector& nums, int left, int right)
整体代码如下：
class Solution {
private:
// 在左闭右开区间[left, right)，构造二叉树
TreeNode* traversal(vector& nums, int left, int right) {
if (left >= right) return nullptr;
// 分割点下标：maxValueIndex
int maxValueIndex = left;
for (int i = left + 1; i < right; ++i) {
if (nums[i] > nums[maxValueIndex]) maxValueIndex = i;
}
TreeNode* root = new TreeNode(nums[maxValueIndex]);
// 左闭右开：[left, maxValueIndex)
root->left = traversal(nums, left, maxValueIndex);
// 左闭右开：[maxValueIndex + 1, right)
root->right = traversal(nums, maxValueIndex + 1, right);
return root;
}
public:
TreeNode* constructMaximumBinaryTree(vector& nums) {
return traversal(nums, 0, nums.size());//左闭右开，相当于区间是0~nums.size()-1.
}
};
用数组构造二叉树的题目，每次分隔尽量不要定义新的数组，而是通过下标索引直接在原数组上操作，这样可以节约时间和空间上的开销。
LeetCode 98. 验证二叉搜索树 LeetCode 98. 验证二叉搜索树 方法1利用性质：中序遍历下，输出的二叉搜索树节点的数值是有序序列。
class Solution {
private:
vector vec;
void traversal(TreeNode* root) {
if (root == NULL) return;
traversal(root->left);
vec.push_back(root->val); // 将二叉搜索树转换为有序数组
traversal(root->right);
}
public:
bool isValidBST(TreeNode* root) {
vec.clear(); // 不加这句在leetcode上也可以过，但最好加上
traversal(root);
for (int i = 1; i < vec.size(); i++) {
// 注意要小于等于，搜索树里不能有相同元素
if (vec[i] <= vec[i - 1]) return false;
}
return true;
}
};
递归中序遍历将二叉搜索树转变成一个数组，然后只要比较一下，这个数组是否是有序的，注意二叉搜索树中不能有重复元素。
！！！我们要比较的是 左子树所有节点小于中间节点，右子树所有节点大于中间节点。
不能单纯的比较左节点小于中间节点，右节点大于中间节点就完事了。
错误示例如下：
//wrong answer!!!
if (root->val > root->left->val && root->val < root->right->val) {
return true;
} else {
return false;
}
方法2
class Solution {
public:
//因为后台数据有int最小值测试用例，所以都把maxVal改成了longlong最小值
long long maxVal = LONG_MIN; // 因为后台测试数据中有int最小值
bool isValidBST(TreeNode* root) {
if (root == NULL) return true;
bool left = isValidBST(root->left);
// 中序遍历，验证遍历的元素是不是从小到大
if (maxVal < root->val) maxVal = root->val;
else return false;
bool right = isValidBST(root->right);
return left && right;
}
};
中序遍历，一直更新maxVal，一旦发现maxVal >= root->val，就返回false，注意元素相同时候也要返回false。
LeetCode 236. 二叉树的最近公共祖先 LeetCode 236. 二叉树的最近公共祖先遇到这个题目首先想的是要是能自底向上查找就好了，这样就可以找到公共祖先了。
二叉树回溯的过程就是自底向上查找。
后序遍历就是天然的回溯过程，最先处理的一定是叶子节点。
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == q || root == p || 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;
if (left == NULL && right != NULL) return right;
else if (left != NULL && right == NULL) return left;
else { // (left == NULL && right == NULL)
return NULL;
}
}
};
如果left 和 right都不为空，说明此时root就是最近公共节点。这个比较好理解
如果left为空，right不为空，就返回right，说明目标节点是通过right返回的，反之依然。
LeetCode 701. 二叉搜索树中的插入操作 LeetCode 701. 二叉搜索树中的插入操作class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
//终止条件就是找到遍历的节点为null的时候，就是要插入节点的位置了，并把插入的节点返回。
if (root == NULL) {
TreeNode* node = new TreeNode(val);
return node;
}
if (root->val > val) root->left = insertIntoBST(root->left, val);
if (root->val < val) root->right = insertIntoBST(root->right, val);
return root;
}
};
LeetCode 450. 删除二叉搜索树中的节点
LeetCode 450. 删除二叉搜索树中的节点
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if(root==nullptr) return root;
if(root->val==key)
{
if (root->left == nullptr && root->right == nullptr) return nullptr;
else if (root->left == nullptr) return root->right;
else if (root->right == nullptr) return root->left;
else
{
TreeNode* cur = root->right; // 找右子树最左面的节点
while(cur->left)
{
cur = cur->left;
}
cur->left = root->left; // 把要删除的节点（root）左子树放在cur的左孩子的位置
root = root->right; // 返回旧root的右孩子作为新root
return root;
}
}
if(root->val>key) root->left=deleteNode(root->left,key);
if(root->valright=deleteNode(root->right,key);
return root;
}
};
- 确定单层递归的逻辑
这里就把二叉搜索树中删除节点遇到的情况都搞清楚。
有以下五种情况：
- 第一种情况：没找到删除的节点，遍历到空节点直接返回了
- 找到删除的节点
- 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
- 第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
- 第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
- 第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
if (root == nullptr ) return nullptr;
//如果root（当前节点）的元素小于low的数值，那么应该递归右子树，并返回右子树符合条件的头结点。
if (root->val < low) {
TreeNode* right = trimBST(root->right, low, high); // 寻找符合区间[low, high]的节点
return right;
}
//如果root(当前节点)的元素大于high的，那么应该递归左子树，并返回左子树符合条件的头结点。
if (root->val > high) {
TreeNode* left = trimBST(root->left, low, high); // 寻找符合区间[low, high]的节点
return left;
}
root->left = trimBST(root->left, low, high); // root->left接入符合条件的左孩子
root->right = trimBST(root->right, low, high); // root->right接入符合条件的右孩子
return root;
}
};
简化之后，如下：
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;
}
};
LeetCode 538. 把二叉搜索树转换为累加树
LeetCode 538. 把二叉搜索树转换为累加树
class Solution {
private:
//需要定义一个全局变量pre，用来保存cur节点的前一个节点的数值
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;
}
};
一个有序数组[2, 5, 13]，求从后到前的累加数组，也就是[20, 18, 13]。
从树中可以看出累加的顺序是右中左，所以我们需要反中序遍历这个二叉树，然后顺序累加就可以了
需要定义一个全局变量pre，用来保存cur节点的前一个节点的数值
