题目链接：点击打开链接
题目大意：略
解题思路：略
相关企业
- 字节跳动
- 亚马逊（Amazon）
- 谷歌（Google）
- 微软（Microsoft）
- 优步（Uber）
- 彭博（Bloomberg）
AC 代码
- 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;* }* }*/// 解决方案(1)classSolution { int[] preorder, inorder; Map<Integer, Integer>inorderMap=newHashMap<>(); publicTreeNodebuildTree(int[] preorder, int[] inorder) { this.preorder=preorder; this.inorder=inorder; for (inti=0; i<inorder.length; i++) { inorderMap.put(inorder[i], i); } returnrecur(0, inorder.length-1, 0, preorder.length-1); } TreeNoderecur(intla, intra, intlb, intrb) { if (la>ra) returnnull; intpreRoot=preorder[lb]; intmidRoot=inorderMap.get(preRoot); intleftLen=midRoot-la; TreeNoderoot=newTreeNode(preRoot); root.left=recur(la, midRoot-1, lb+1, lb+leftLen); root.right=recur(midRoot+1, ra, lb+leftLen+1, rb); returnroot; } } // 解决方案(2)classSolution { int[] preorder; HashMap<Integer, Integer>dic=newHashMap<>(); publicTreeNodebuildTree(int[] preorder, int[] inorder) { this.preorder=preorder; for(inti=0; i<inorder.length; i++) dic.put(inorder[i], i); returnrecur(0, 0, inorder.length-1); } TreeNoderecur(introot, intleft, intright) { if(left>right) returnnull; // 递归终止TreeNodenode=newTreeNode(preorder[root]); // 建立根节点inti=dic.get(preorder[root]); // 划分根节点、左子树、右子树node.left=recur(root+1, left, i-1); // 开启左子树递归node.right=recur(root+i-left+1, i+1, right); // 开启右子树递归, root + i - left + 1 => root + (left - (i - 1) + 1) + 1 (根节点索引 + 左子树长度 + 1)returnnode; // 回溯返回根节点 } }
- 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) {}* };*/classSolution { public: TreeNode*buildTree(vector<int>&preorder, vector<int>&inorder) { this->preorder=preorder; for(inti=0; i<inorder.size(); i++) dic[inorder[i]] =i; returnrecur(0, 0, inorder.size() -1); } private: vector<int>preorder; unordered_map<int, int>dic; TreeNode*recur(introot, intleft, intright) { if(left>right) returnnullptr; // 递归终止TreeNode*node=newTreeNode(preorder[root]); // 建立根节点inti=dic[preorder[root]]; // 划分根节点、左子树、右子树node->left=recur(root+1, left, i-1); // 开启左子树递归node->right=recur(root+i-left+1, i+1, right); // 开启右子树递归, root + i - left + 1 => root + (left - (i - 1) + 1) + 1 (根节点索引 + 左子树长度 + 1)returnnode; // 回溯返回根节点 } };
