1、先序，中序遍歷確定二叉樹

105

方法一、

前提

• ① 必須不能有重復(fù)元素
• ② 只有先序＋中序和后序＋中序才能實(shí)現(xiàn)唯一樹

思考要點(diǎn)：

• 不要想著用for循環(huán)，遞歸一定更好解決
• 輸入是vector，遞歸就得考慮傳入索引

class Solution {  
public:  // 輔助函數(shù)，構(gòu)建子樹  TreeNode* build_subTree(vector<int>& preorder, unordered_map<int, int>& inorder_map, int pre_st, int in_st, int in_end) {  // 如果當(dāng)前中序遍歷的起始位置大于結(jié)束位置，返回空指針  if (in_st > in_end) return nullptr;  // 創(chuàng)建根節(jié)點(diǎn)，使用前序遍歷數(shù)組中的當(dāng)前元素  TreeNode* root = new TreeNode(preorder[pre_st]);  // 獲取當(dāng)前根節(jié)點(diǎn)在中序遍歷中的索引  int inorderRootIndex = inorder_map[preorder[pre_st]];   // 遞歸構(gòu)建左子樹  root->left = build_subTree(preorder, inorder_map, pre_st + 1, in_st, inorderRootIndex - 1);  // 遞歸構(gòu)建右子樹  root->right = build_subTree(preorder, inorder_map, pre_st + (inorderRootIndex - in_st) + 1, inorderRootIndex + 1, in_end);  // 返回構(gòu)建好的子樹根節(jié)點(diǎn)  return root;  }  // 主函數(shù)，構(gòu)建二叉樹  TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {  // 創(chuàng)建一個(gè)哈希表，用于快速查找中序遍歷中每個(gè)值的索引  unordered_map<int, int> inorder_map;  for (int i = 0; i < inorder.size(); i++) {  inorder_map[inorder[i]] = i; // 存儲(chǔ)每個(gè)節(jié)點(diǎn)值到其索引的映射  }  // 調(diào)用輔助函數(shù)構(gòu)建樹，初始始點(diǎn)為0，結(jié)束點(diǎn)為中序遍歷的最后一個(gè)索引  return build_subTree(preorder, inorder_map, 0, 0, inorder.size() - 1);  }  
};  

2、中序，后序確定二叉樹

和上文的思路相似。

/**  * Definition for a binary tree node.  * struct TreeNode {  *     int val;               // 節(jié)點(diǎn)的值  *     TreeNode *left;       // 左子樹的指針  *     TreeNode *right;      // 右子樹的指針  *     TreeNode() : val(0), left(nullptr), right(nullptr) {} // 默認(rèn)構(gòu)造函數(shù)  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} // 帶值構(gòu)造函數(shù)  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} // 帶值和左右子樹構(gòu)造函數(shù)  * };  */  
class Solution {  
public:  // 遞歸構(gòu)建子樹的輔助函數(shù)  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; // 如果當(dāng)前子樹的中序范圍無效，返回空指針  TreeNode* root = new TreeNode(postorder[post_end]); // 取后序遍歷最后一個(gè)元素作為當(dāng)前子樹的根節(jié)點(diǎn)  int inorder_root_index = inorder_map[postorder[post_end]]; // 找到根節(jié)點(diǎn)在中序遍歷中的索引  root->right = buildsubtree(postorder, inorder_map, post_end - 1, inorder_root_index + 1, in_end); // 遞歸構(gòu)建右子樹  root->left = buildsubtree(postorder, inorder_map, post_end - (in_end - inorder_root_index) - 1, in_st, inorder_root_index - 1); // 遞歸構(gòu)建左子樹  return root; // 返回當(dāng)前構(gòu)建的根節(jié)點(diǎn)  }  // 主函數(shù)，接受中序和后序遍歷數(shù)組并返回構(gòu)建的二叉樹  TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {  unordered_map<int,int> inorder_map; // 用于存儲(chǔ)中序遍歷的元素及其索引  int len = postorder.size(); // 獲取后序遍歷數(shù)組的長度  for (auto i = 0; i < inorder.size(); i++) {  inorder_map[inorder[i]] = i; // 每個(gè)元素的值和對(duì)應(yīng)的索引  }  return buildsubtree(postorder, inorder_map, len - 1, 0, len - 1); // 調(diào)用輔助函數(shù)從后序數(shù)組的最后一個(gè)元素開始構(gòu)建樹  }  
};

有相同點(diǎn)：

• 均為分左右子樹各自遞歸。
• map都是由中序遍歷來擔(dān)任。只不過前序找根節(jié)點(diǎn)是從前往后，后序則是從后往前。

不同點(diǎn)：
前序是先構(gòu)造左子樹；
后序是先構(gòu)造右子樹。

root->right = buildsubtree(postorder, inorder_map, post_end - 1, inorder_root_index + 1, in_end); // 遞歸構(gòu)建右子樹  
root->left = buildsubtree(postorder, inorder_map, post_end - (in_end - inorder_root_index) - 1, in_st, inorder_root_index - 1); // 遞歸構(gòu)建左子樹  

3、二叉樹展開為鏈表

114

二叉樹展開成為鏈表

114

方法一、

用先序遍歷方法將樹讀出先，這里要掌握先序讀取樹，其中就要應(yīng)用到引用&，不然遞歸會(huì)爆內(nèi)存，然后再進(jì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 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();  // 記得要把第一個(gè)去掉噢build_tree(root,front_num);}
};