二叉树（中等题）

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);}
};