网站建设企划动力,网站交互是什么,网络营销服务的特点,石家庄网络公司招聘Leetcode hot100 二叉树1.二叉搜索树中第K小的元素2.二叉树展开为链表3.从前序与中序遍历序列构造二叉树 二叉树
1.二叉搜索树中第K小的元素
二叉搜索树中第K小的元素
最重要的知识点#xff1a;二叉树搜索树的中序遍历是升序的。 方法一#xff1a;我们只需存储升序遍历二叉树搜索树的中序遍历是升序的。 方法一我们只需存储升序遍历返回升序遍历的结果即可。
/*** 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:vectorint ans;int kthSmallest(TreeNode* root, int k) {dfs(root);return ans[k - 1];}void dfs(TreeNode* root) {if (root nullptr) return;dfs(root-left);ans.push_back(root-val);dfs(root-right); }
};改进我们还可以在找到答案后停止不需要遍历整棵树。
/*** 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 ans;int kthSmallest(TreeNode* root, int k) {dfs(root, k);return ans;}void dfs(TreeNode* root, int k) {if (root nullptr) return;dfs(root-left, k);if (--k 0) {ans root-val;return;}dfs(root-right, k); }
};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:void flatten(TreeNode* root) {vectorTreeNode* ans;dfs(root, ans);for (int i 1; i ans.size(); i) {//前一个节点auto *pre ans.at(i - 1);//当前节点auto *cur ans.at(i);pre-left nullptr;pre-right cur; }}void dfs(TreeNode* root, vectorTreeNode* ans) {if (root nullptr) return;ans.push_back(root);dfs(root-left, ans);dfs(root-right, ans); }
};思路二更便捷的递归 参考 这个问题其实是分为三步
首先将根节点的左子树变成链表其次将根节点的右子树变成链表最后将变成链表的右子树放在变成链表的左子树的最右边
这就是一个递归的过程递归的一个非常重要的点就是不去管函数的内部细节是如何处理的我们只看其函数作用以及输入与输出。对于函数flatten来说
函数作用将一个二叉树原地将它展开为链表 输入树的根节点 输出无
/*** 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) {if (root nullptr) return;//展开左子树为链表flatten(root-left);//展开子树为链表flatten(root-right);auto l root-left;auto r root-right;//左子树置空root-left nullptr;//左子树移动到右子树root-right l;//指针指向右子树最后一个节点while (root-right ! nullptr) root root-right;//指向右子树root-right r;}
};3.从前序与中序遍历序列构造二叉树
从前序与中序遍历序列构造二叉树 根据前序和中序遍历我们可以确定二叉树的根节点左子树和右子树不断递归得到结果。比较复杂的是确定左右子树的边界。借助map来快速确定元素在inorder中的位置这副图中的边界位置建议仔细推导。 需要注意的点前序遍历中左子树的右边界 需要借助 中序遍历中 左子树的个数 来辅助确定。
/*** 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(vectorint preorder, vectorint inorder) {int n preorder.size();if (!n) return nullptr;unordered_mapint, int mp;for (int i 0; i n; i) {mp[inorder[i]] i;}return dfs(preorder, 0, n - 1, mp, 0, n - 1);}TreeNode* dfs(vectorint preorder, int preleft, int preright,unordered_mapint, int mp, int inleft, int intright) {if (preright preleft || inleft intright) return nullptr;TreeNode* ans new TreeNode(preorder[preleft]);ans-left dfs(preorder, preleft 1, mp[preorder[preleft]] preleft - inleft, mp, inleft, mp[preorder[preleft]] - 1);ans-right dfs(preorder, mp[preorder[preleft]] preleft - inleft 1, preright, mp, mp[preorder[preleft]] 1, intright);return ans;}};
