海报制作app/seo课程哪个好

两种方法：

一、递归

有先序序列得到根节点的值，创建根节点，再递归构造左子树，右子树。 由先序得到根结点，再在中序序列找到根节点，根节点左边就是左子树，右边就是右子树。

在中序序列中找根节点，就可以用到哈希结构，这里是想得到她的坐标，所以value存坐标。

Java:

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {private Map<Integer,Integer> indexMap;public TreeNode myBuildTree(int[] preorder,int[] inorder,int preLeft,int preRight,int inLeft,int inRight){if(preLeft>preRight||inLeft>inRight) return null;int pre_rootindex=preLeft;int in_rootindex=indexMap.get(preorder[preLeft]);TreeNode root=new TreeNode(preorder[preLeft]);root.left=myBuildTree(preorder,inorder,preLeft+1,in_rootindex-inLeft+pre_rootindex,inLeft,in_rootindex-1);root.right=myBuildTree(preorder,inorder,in_rootindex-inLeft+pre_rootindex+1,preRight,in_rootindex+1,inRight);return root;}public TreeNode buildTree(int[] preorder, int[] inorder) {int n=preorder.length;indexMap=new HashMap<Integer,Integer>();for(int i=0;i<n;i++){indexMap.put(inorder[i],i);}return myBuildTree(preorder,inorder,0,n-1,0,n-1);}
}

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 {
private: unordered_map<int,int> indexMap;
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int n=preorder.size();//indexMap=new HashMap<Integer,Integer>();for(int i=0;i<n;i++){indexMap.emplace(inorder[i],i);}return myBuildTree(preorder,inorder,0,n-1,0,n-1);}TreeNode* myBuildTree(vector<int> preorder,vector<int> inorder,int preLeft,int preRight,int inLeft,int inRight){if(preLeft>preRight||inLeft>inRight) return nullptr;int pre_rootindex=preLeft;int in_rootindex=indexMap.at(preorder[preLeft]);TreeNode *root=new TreeNode(preorder[preLeft]);root->left=myBuildTree(preorder,inorder,preLeft+1,in_rootindex-inLeft+pre_rootindex,inLeft,in_rootindex-1);root->right=myBuildTree(preorder,inorder,in_rootindex-inLeft+pre_rootindex+1,preRight,in_rootindex+1,inRight);return root;}
};

二、迭代，用到栈

先序：根左右   <-

中序：左根右   -> 

题解见https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by--22/ 

补充：当先序与中序相等时，此结点为某结点的右子树，寻找父节点的方法是：倒序遍历先序（栈中的先序），正序遍历中序，两者最后一个相等的结点即为父节点.

Java:

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {if(preorder==null||preorder.length==0) return null;TreeNode root=new TreeNode(preorder[0]);Deque<TreeNode> stack=new LinkedList<TreeNode>();stack.push(root);int inorderIndex=0;for(int i=1;i<preorder.length;i++){int preorderVal=preorder[i];//待判断的结点TreeNode node=stack.peek();//栈顶结点if(node.val!=inorder[inorderIndex]){//先序与中序不相等，则为左子树node.left=new TreeNode(preorderVal);stack.push(node.left);}else{//相等，则为某个节点的右子树，寻找该父节点while(!stack.isEmpty()&&stack.peek().val==inorder[inorderIndex]){node=stack.pop();inorderIndex++;}node.right=new TreeNode(preorderVal);stack.push(node.right);}}return root;}
}

 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* buildTree(vector<int>& preorder, vector<int>& inorder) {if(preorder.size()==0||inorder.size()==0) return nullptr;stack<TreeNode*> sta;TreeNode* root=new TreeNode(preorder[0]);sta.push(root);int inorderIndex=0;for(int i=1;i<preorder.size();i++){TreeNode* node=sta.top();if(node->val!=inorder[inorderIndex]){node->left=new TreeNode(preorder[i]);sta.push(node->left);}else{while(!sta.empty()&&sta.top()->val==inorder[inorderIndex]){node=sta.top();sta.pop();inorderIndex++;}node->right=new TreeNode(preorder[i]);sta.push(node->right);}}return root;}
};