每个题目都用 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);
}
};
