网站推广的方法及特点_怎么介绍自己的家乡_怎样利用互联网进行网络推广_长沙大型网站建设公司

题目描述

给定两个整数数组 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]

提示:

• 1 <= inorder.length <= 3000
• postorder.length == inorder.length
• -3000 <= inorder[i], postorder[i] <= 3000
• inorder 和 postorder 都由 不同 的值组成
• postorder 中每一个值都在 inorder 中
• inorder 保证是树的中序遍历
• postorder 保证是树的后序遍历

思路

递归法

递归法步骤：

• 第一步：如果数组大小为零的话，说明是空节点了。

• 第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。

• 第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点

• 第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）

• 第五步：切割后序数组，切成后序左数组和后序右数组

• 第六步：递归处理左区间和右区间

代码

C++版：

/*** 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* traversal(vector<int>& inorder, vector<int>& postorder){// 第一步，判断是否为空节点if(postorder.size()==0) return NULL;// 第二步，取后序数组最后一个元素作为节点元素int rootValue=postorder[postorder.size()-1];TreeNode* root=new TreeNode(rootValue);// 仅有一个节点if(postorder.size()==1) return root;// 第三步，找切割点int i;for(i=0;i<inorder.size();i++){if(inorder[i]==rootValue) break;}// 第四步，切割中序数组，得到中序左数组[0, i)和中序右数组[i+1,end)，vector<int> leftInorder(inorder.begin(),inorder.begin() + i);vector<int> rightInorder(inorder.begin()+i+1,inorder.end());// postorder 舍弃末尾元素postorder.resize(postorder.size() - 1);// 第五步，切割后序数组，得到后序左数组和后序右数组vector<int> leftPostorder(postorder.begin(), postorder.begin()+leftInorder.size());vector<int> rightPostorder(postorder.begin()+leftInorder.size(), postorder.end());// 第六步，递归处理左区间和右区间root->left = traversal(leftInorder, leftPostorder);root->right = traversal(rightInorder, rightPostorder);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if(inorder.size()==0 || postorder.size()==0) return NULL;return traversal(inorder,postorder);}
};

Python版：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:# 第一步: 特殊情况讨论: 树为空. (递归终止条件)if not postorder:return None# 第二步: 后序遍历的最后一个就是当前的中间节点.root_val = postorder[-1]root = TreeNode(root_val)# 第三步: 找切割点.separator_idx = inorder.index(root_val)# 第四步: 切割inorder数组. 得到inorder数组的左,右半边.inorder_left = inorder[:separator_idx]inorder_right = inorder[separator_idx + 1:]# 第五步: 切割postorder数组. 得到postorder数组的左,右半边.postorder_left = postorder[:len(inorder_left)]postorder_right = postorder[len(inorder_left): len(postorder) - 1]# 第六步: 递归root.left = self.buildTree(inorder_left, postorder_left)root.right = self.buildTree(inorder_right, postorder_right)return root

需要注意的地方

1.由于中序数组大小一定是和后序数组的大小相同的，将中序数组切成了左中序数组和右中序数组后，后序数组就可以按照左中序数组的大小来切割，切成左后序数组和右后序数组。

2.使用索引来代替新建数组会更省时间。