1、先序，中序遍历确定二叉树
105
方法一、
前提
- ① 必须不能有重复元素
- ② 只有先序＋中序和后序＋中序才能实现唯一树
思考要点：
- 不要想着用for循环，递归一定更好解决
- 输入是vector，递归就得考虑传入索引
class Solution {
public: // 辅助函数，构建子树 TreeNode* build_subTree(vector<int>& preorder, unordered_map<int, int>& inorder_map, int pre_st, int in_st, int in_end) { // 如果当前中序遍历的起始位置大于结束位置，返回空指针 if (in_st > in_end) return nullptr; // 创建根节点，使用前序遍历数组中的当前元素 TreeNode* root = new TreeNode(preorder[pre_st]); // 获取当前根节点在中序遍历中的索引 int inorderRootIndex = inorder_map[preorder[pre_st]]; // 递归构建左子树 root->left = build_subTree(preorder, inorder_map, pre_st + 1, in_st, inorderRootIndex - 1); // 递归构建右子树 root->right = build_subTree(preorder, inorder_map, pre_st + (inorderRootIndex - in_st) + 1, inorderRootIndex + 1, in_end); // 返回构建好的子树根节点 return root; } // 主函数，构建二叉树 TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { // 创建一个哈希表，用于快速查找中序遍历中每个值的索引 unordered_map<int, int> inorder_map; for (int i = 0; i < inorder.size(); i++) { inorder_map[inorder[i]] = i; // 存储每个节点值到其索引的映射 } // 调用辅助函数构建树，初始始点为0，结束点为中序遍历的最后一个索引 return build_subTree(preorder, inorder_map, 0, 0, inorder.size() - 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: // 递归构建子树的辅助函数 TreeNode* buildsubtree(vector<int>& postorder, unordered_map<int,int>& inorder_map, int post_end, int in_st, int in_end) { if (in_st > in_end) return nullptr; // 如果当前子树的中序范围无效，返回空指针 TreeNode* root = new TreeNode(postorder[post_end]); // 取后序遍历最后一个元素作为当前子树的根节点 int inorder_root_index = inorder_map[postorder[post_end]]; // 找到根节点在中序遍历中的索引 root->right = buildsubtree(postorder, inorder_map, post_end - 1, inorder_root_index + 1, in_end); // 递归构建右子树 root->left = buildsubtree(postorder, inorder_map, post_end - (in_end - inorder_root_index) - 1, in_st, inorder_root_index - 1); // 递归构建左子树 return root; // 返回当前构建的根节点 } // 主函数，接受中序和后序遍历数组并返回构建的二叉树 TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { unordered_map<int,int> inorder_map; // 用于存储中序遍历的元素及其索引 int len = postorder.size(); // 获取后序遍历数组的长度 for (auto i = 0; i < inorder.size(); i++) { inorder_map[inorder[i]] = i; // 每个元素的值和对应的索引 } return buildsubtree(postorder, inorder_map, len - 1, 0, len - 1); // 调用辅助函数从后序数组的最后一个元素开始构建树 }
};
有相同点：
- 均为分左右子树各自递归。
- map都是由中序遍历来担任。只不过前序找根节点是从前往后，后序则是从后往前。
不同点：
前序是先构造左子树；
后序是先构造右子树。
root->right = buildsubtree(postorder, inorder_map, post_end - 1, inorder_root_index + 1, in_end); // 递归构建右子树
root->left = buildsubtree(postorder, inorder_map, post_end - (in_end - inorder_root_index) - 1, in_st, inorder_root_index - 1); // 递归构建左子树
3、二叉树展开为链表
114
二叉树展开成为链表
114
方法一、
用先序遍历方法将树读出先，这里要掌握先序读取树，其中就要应用到引用&，不然递归会爆内存，然后再进行建树
/*** 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 front_read(TreeNode*root, queue<int>& next_one){if(root==nullptr)return;next_one.push(root->val);front_read(root->left,next_one);front_read(root->right,next_one);}void build_tree(TreeNode*root,queue<int>&front_num){if(front_num.size()>0){TreeNode* right_son = new TreeNode(front_num.front());root->right=right_son;front_num.pop();build_tree(root->right,front_num);}}void flatten(TreeNode* root) {if(root==nullptr)return;queue<int> front_num;front_read(root,front_num);root->left=nullptr;front_num.pop(); // 记得要把第一个去掉噢build_tree(root,front_num);}
};
