1. 从中序与后序遍历序列构造二叉树
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
出处：
https://edu.csdn.net/practice/26654112
代码：
#define null INT_MIN #include <bits/stdc++.h> using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; class Solution { public: TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) { if (0 == inorder.size() || 0 == postorder.size()) { return NULL; } return build(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1); } TreeNode *build(vector<int> &inorder, int i1, int i2, vector<int> &postorder, int p1, int p2) { TreeNode *root = new TreeNode(postorder[p2]); int i = i1; while (i <= i2 && postorder[p2] != inorder[i]) { i++; } int left = i - i1; int right = i2 - i; if (left > 0) { root->left = build(inorder, i1, i - 1, postorder, p1, p1 + left - 1); } if (right > 0) { root->right = build(inorder, i + 1, i2, postorder, p1 + left, p2 - 1); } return root; } }; vector<int> preorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> st; st.push(root); while (!st.empty()) { TreeNode* node = st.top(); st.pop(); if (node != nullptr) { res.push_back(node->val); st.push(node->right); st.push(node->left); } } return res; } string vectorToString(vector<int> vect) { stringstream ss; ss << "["; for (size_t i = 0; i < vect.size(); i++) { ss << vect[i] << (i < vect.size() - 1 ? "," : ""); } ss << "]"; return ss.str(); } int main() { Solution s; vector<int> inorder = {9,3,15,20,7}; vector<int> postorder = {9,15,7,20,3}; TreeNode* root = s.buildTree(inorder, postorder); vector<int> preorder = preorderTraversal(root); cout << vectorToString(preorder) << endl; return 0; }
输出：
[3,9,20,15,7]
2. 从先序与中序遍历序列构造二叉树
根据一棵树的先序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
先序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
出处：
与上题类似，已知三种遍历中的两个且有中序，就能确定一棵二叉树。如果只有先序、后序，因为不能确定根的位置，所以无法确定。
代码：
#define null INT_MIN #include <bits/stdc++.h> using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; class Solution { public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { if (preorder.empty() || inorder.empty()) { return nullptr; } unordered_map<int, int> pos; for (int i = 0; i < (int)inorder.size(); ++i) { pos[inorder[i]] = i; } return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1, pos); } TreeNode* build(vector<int>& preorder, int p1, int p2, vector<int>& inorder, int i1, int i2, unordered_map<int, int>& pos) { if (p1 > p2 || i1 > i2) { return nullptr; } int rootVal = preorder[p1]; int i = pos[rootVal]; TreeNode* root = new TreeNode(rootVal); root->left = build(preorder, p1 + 1, p1 + i - i1, inorder, i1, i - 1, pos); root->right = build(preorder, p1 + i - i1 + 1, p2, inorder, i + 1, i2, pos); return root; } }; vector<int> postorderTraversal(TreeNode* root) { vector<int> res; if (root == nullptr) { return res; } stack<TreeNode*> st1, st2; st1.push(root); while (!st1.empty()) { TreeNode* node = st1.top(); st1.pop(); st2.push(node); if (node->left != nullptr) { st1.push(node->left); } if (node->right != nullptr) { st1.push(node->right); } } while (!st2.empty()) { res.push_back(st2.top()->val); st2.pop(); } return res; } string vectorToString(vector<int> vect) { stringstream ss; ss << "["; for (size_t i = 0; i < vect.size(); i++) { ss << vect[i] << (i < vect.size() - 1 ? "," : ""); } ss << "]"; return ss.str(); } int main() { Solution s; vector<int> preorder = {3,9,20,15,7}; vector<int> inorder = {9,3,15,20,7}; TreeNode* root = s.buildTree(preorder, inorder); vector<int> postorder = postorderTraversal(root); cout << vectorToString(postorder) << endl; return 0; }
输出：
[9,15,7,20,3]
3. 二叉树展开为链表
给你二叉树的根结点 root ，请你将它展开为一个单链表：
- 展开后的单链表应该同样使用
TreeNode，其中right子指针指向链表中下一个结点，而左子指针始终为null。 - 展开后的单链表应该与二叉树 先序遍历 顺序相同。
示例 1：
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [0]
输出：[0]
提示：
树中结点数在范围 [0, 2000] 内
-100 <= Node.val <= 100
进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？
出处：
https://edu.csdn.net/practice/25405424
代码：
#define null INT_MIN #include <bits/stdc++.h> using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; class Solution { public: void rconnect(TreeNode *&node, TreeNode *pmove) { if (pmove == nullptr) return; node->right = new TreeNode(pmove->val); node->left = nullptr; node = node->right; rconnect(node, pmove->left); rconnect(node, pmove->right); } void flatten(TreeNode *root) { if (root == nullptr) return; TreeNode *head = new TreeNode(null); TreeNode *newroot = head; rconnect(head, root); newroot = newroot->right->right; root->right = newroot; root->left = nullptr; } }; TreeNode* buildTree(vector<int>& nums) { if (nums.empty()) return nullptr; TreeNode *root = new TreeNode(nums.front()); queue<TreeNode*> q; q.push(root); int i = 1; while(!q.empty() && i < nums.size()) { TreeNode *cur = q.front(); q.pop(); if(i < nums.size() && nums[i] != null) { cur->left = new TreeNode(nums[i]); q.push(cur->left); } i++; if(i < nums.size() && nums[i] != null) { cur->right = new TreeNode(nums[i]); q.push(cur->right); } i++; } return root; } vector<int> preorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> st; st.push(root); while (!st.empty()) { TreeNode* node = st.top(); st.pop(); if (node != nullptr) { res.push_back(node->val); st.push(node->right); st.push(node->left); } else res.push_back(null); } while (res.back()==null) res.pop_back(); return res; } string vectorToString(vector<int> vect) { stringstream ss; ss << "["; for (size_t i = 0; i < vect.size(); i++) { ss << (vect[i] == null ? "null" : to_string(vect[i])); ss << (i < vect.size() - 1 ? "," : "]"); } return ss.str(); } int main() { Solution s; vector<int> nums = {1,2,5,3,4,null,6}; TreeNode* root = buildTree(nums); s.flatten(root); cout << vectorToString(preorderTraversal(root)) << endl; return 0; }
输出：
[1,null,2,null,3,null,4,null,5,null,6]
