每个题目都用 2~3 种解法做出来,太费时间了,以后只用 1~2 种解法....
目录
🌼有序数组转二叉搜索树
AC 二分递归
🚩验证二叉搜索树
AC 递归
🌼二叉搜索树中的第 k 小元素
AC 中序遍历 -- 栈
🎂二叉树的右视图
AC 层序遍历
🥤二叉树展开为链表
AC 辅助数组
🌼有序数组转二叉搜索树
108. 将有序数组转换为二叉搜索树 - 力扣(LeetCode)
二叉搜索树 -- 中序遍历(左-根-右)升序
左子树 < 根 < 右子树
查 和 增删改,都是 O(logn)
本题只涉及 Insert() 和 Create()
如果数组是无序的,插入 n 个元素,每次插入 O(logn),总的时间复杂度就是 O(nlogn)
但是本题是有序的...
AC 二分递归
数组升序,直接二分,时间 O(n) -- 每个节点只访问 1 次;空间 O(logn) -- 递归栈深度
/**
* 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* sortedArrayToBST(vector<int>& nums) {
int n = nums.size();
return dfs(0, n-1, nums);
}
TreeNode* dfs(int l, int r, vector<int>& nums) {\
// 递归出口
if (l > r) return nullptr;
int mid = (l + r) >> 1;
TreeNode* T = new TreeNode(nums[mid]); // 根
// 记得赋值
T->left = dfs(l, mid - 1, nums); // 递归左子树
T->right = dfs(mid + 1, r, nums); // 递归右子树
return T;
}
};
🚩验证二叉搜索树
98. 验证二叉搜索树 - 力扣(LeetCode)
AC 递归
引入了最大值 upper(LONG_MAX) 和最小值 lower(LONG_MIN),避免每次判断时,还需要讨论左右子树
更新时,将最大 / 小值,更新为当前节点的 root->val
递归左子树,更新最大值 upper
递归右子树,更新最小值 lower
函数参数:helper(root, lower, upper)
时间 O(n) -- 每个节点访问 1 次;空间 O(n) -- 递归栈深度,即二叉树高度,最坏一长条
/**
* 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:
bool helper(TreeNode* root, long long l, long long r) {
// 递归出口
if (!root)
return true;
if (root->val <= l || root->val >= r) // 超过区间范围
return false;
return helper(root->left, l, root->val)
&& helper(root->right, root->val, r);
}
bool isValidBST(TreeNode* root) {
return helper(root, LONG_MIN, LONG_MAX);
}
};
🌼二叉搜索树中的第 k 小元素
230. 二叉搜索树中第K小的元素 - 力扣(LeetCode)
AC 中序遍历 -- 栈
栈实现中序遍历,通过 k-- 找到第 k 小元素,k == 0 时输出 root->val
1)内层 while 找到最左节点,即最小节点
2)遍历最小节点右子树 root->right
重复上述 1) 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:
int kthSmallest(TreeNode* root, int k) {
stack<TreeNode*> st;
// 循环 -- 直到所有节点都遍历过
while (root || !st.empty()) {
// 找到最左节点
while (root) {
st.push(root);
root = root->left;
}
root = st.top();
st.pop(); // 升序出栈
k--;
if (k == 0)
break;
root = root->right; // 遍历最小节点--右子树
}
return root->val;
}
};
时间 O(H + k),H 为二叉树高度。平衡树时,H == logN;线性树,H == N
所以时间 O(logN + k) ~ O(N + k)
空间 O(H),同样,根据平衡树 ~ 线性树,O(logN) ~ O(N)
🎂二叉树的右视图
199. 二叉树的右视图 - 力扣(LeetCode)
AC 层序遍历
自顶向下,找每层的最右节点,层序遍历...
通过 int size 统计每层元素个数,只输出最后一个
时空 O(n)
/**
* 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:
vector<int> ans;
vector<int> rightSideView(TreeNode* root) {
queue<TreeNode*> q; // 借助队列实现 bfs 层序遍历
if (!root)
return ans;
q.push(root); // 根节点入队
int size = 1; // 第1层节点数
// 一层一层拓展
while (!q.empty()) {
// 取队头
TreeNode* node = q.front();
q.pop();
size--;
// 拓展左右子树
if (node->left)
q.push(node->left);
if (node->right)
q.push(node->right);
// 插入本层最后一个节点
if (size == 0) {
ans.push_back(node->val);
size = q.size();
}
}
return ans;
}
};
🥤二叉树展开为链表
114. 二叉树展开为链表 - 力扣(LeetCode)
AC 辅助数组
vector 保存先序遍历得到的节点,然后 for 循环:
节点->left = nullptr; 节点->right = 下一节点
第 19 行
TreeNode *pre = vec[i - 1], *cur = vec[i];
声明在 for 循环里,避免了对 0,1 个元素的讨论,n >= 2 才能进入 for 循环
时空 O(n)
/**
* 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:
void flatten(TreeNode* root) {
vector<TreeNode*> vec;
preorder(root, vec);
int n = vec.size();
for (int i = 1; i < n; ++i) {
TreeNode *pre = vec[i - 1], *cur = vec[i];
pre->left = nullptr;
pre->right = cur;
}
}
void preorder(TreeNode* r, vector<TreeNode*> &v) {
if (!r)
return; // 递归出口
// 先序遍历:根->左->右
v.push_back(r);
preorder(r->left, v);
preorder(r->right, v);
}
};