C/C++每日一练(20230427) 二叉树专场（5）

目录

1. 从中序与后序遍历序列构造二叉树  🌟🌟

2. 从先序与中序遍历序列构造二叉树  🌟🌟

3. 二叉树展开为链表  🌟🌟

🌟 每日一练刷题专栏 🌟

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

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]

🌟 每日一练刷题专栏 🌟

✨ 持续，努力奋斗做强刷题搬运工！

👍 点赞，你的认可是我坚持的动力！ 

🌟 收藏，你的青睐是我努力的方向！ 

✎ 评论，你的意见是我进步的财富！  

☸ 主页：https://hannyang.blog.csdn.net/文章来源地址https://www.toymoban.com/news/detail-428203.html

	Golang每日一练 专栏
	Python每日一练 专栏
	C/C++每日一练 专栏
	Java每日一练 专栏

到了这里，关于C/C++每日一练(20230427) 二叉树专场（5）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！