LeetCode（算法）- 105. 从前序与中序遍历序列构造二叉树

/*** 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;                                           // 回溯返回根节点    }
}

/*** 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;                                            // 回溯返回根节点    }
};