代码随想录_二叉树_leetcode105 106

leetcode105. 从前序与中序遍历序列构造二叉树

105. 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

 代码

// leetcode105. 从前序与中序遍历序列构造二叉树
// 递归回溯
class Solution {
public:TreeNode* traversal(vector<int>& preorder, vector<int>& inorder){int size = preorder.size();if (size == 0){return nullptr;}TreeNode* cur = new TreeNode(preorder[0]); //确定根结点int index = 0;for (index = 0; index < size; index++){if (inorder[index] == cur->val){break;}}// 左子树的前序序列和中序序列vector<int> leftPreorder(preorder.begin() + 1, preorder.begin() + index + 1);vector<int> leftInorder(inorder.begin(), inorder.begin() + index);// 右子树的前序序列和中序序列vector<int> rightPreorder(preorder.begin() + index + 1, preorder.end());vector<int> rightInorder(inorder.begin() + index + 1, inorder.end());cur->left = traversal(leftPreorder, leftInorder);cur->right = traversal(rightPreorder, rightInorder);return cur;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {return traversal(preorder, inorder);}
};

leetcode 106. 从中序与后序遍历序列构造二叉树

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

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

示例 2:

输入：inorder = [-1], postorder = [-1]
输出：[-1]

 代码

// leetcode 106. 从中序与后序遍历序列构造二叉树
// 递归
class Solution {
public:TreeNode* traversal(vector<int> inorder, vector<int> postorder){int size = inorder.size();if (size == 0){return nullptr;}TreeNode* cur = new TreeNode(postorder[size - 1]); //找到根结点if (size == 1){return cur;}int index = 0; //从前序遍历中找到根节点 然后分割左右子树for (index = 0; index < size; index++){if (inorder[index] == cur->val){break;}}// 左子树的中序序列和后续序列vector<int> leftInorder(inorder.begin(), inorder.begin() + index);vector<int> leftPostorder(postorder.begin(), postorder.begin() + index);// 右子树的中序序列和后续序列vector<int> rightInorder(inorder.begin() + index + 1, inorder.end());vector<int> rightPostorder(postorder.begin() + index, postorder.end() - 1);cur->left = traversal(leftInorder, leftPostorder);cur->right = traversal(rightInorder, rightPostorder);return cur;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {return traversal(inorder, postorder);}
};