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