博文中会简要介绍Leetcode P0105题目分析及解题思路。
“Construct Binary Tree from Preorder and Inorder Traversal”是一道比较经典的题目。一个二叉树可以通过其前序遍历的序列和中序遍历的序列还原出来。解题的核心思想是运用递归回溯法。
Given preorder and inorder traversal of a tree, construct the binary tree.
Note: You may assume that duplicates do not exist in the tree.
For example, given
preorder = [3,9,20,15,7] inorder = [9,3,15,20,7]Return the following binary tree:
3 / \ 9 20 / \ 15 7
这道题递归回溯思路其实非常直接明了，具体思路如下：
抽象地来看，我们有两个数组，一个是PRE，另一个是IN。
我们能知道的是，PRE这个存储前序遍历的数组，其PRE[0]一定是当前树的根结点，那么如果我们能在IN这个存储中序遍历的数组中找到这个根结点，我们可以说IN数组里，在这个根结点左边的所有结点会形成这个根结点的左子树，反之则形成右子树。
于是我们的任务就简化为，在用PRE[0]作为根结点，在IN中找到根结点，比方说在下标root，用IN[start:root]形成左子树，IN[root+1:end]形成右子树，然后递归地在左右子树里重复上述操作。
以下是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) {
return this.construct(preorder, inorder, 0, inorder.length-1, 0);
}
private TreeNode construct(int[] preorder, int[] inorder, int left, int right, int preRootIdx) {
if (left > right)
return null;
else if (left == right)
return new TreeNode(inorder[left]);
else {
int rootVal = preorder[preRootIdx];
int inRootIdx = -1;
for (int itr=left; itr<=right; ++itr) {
if (inorder[itr] == rootVal) {
inRootIdx = itr;
break;
}
}
int leftPreRootIdx = preRootIdx+1;
int rightPreRootIdx = preRootIdx+(inRootIdx-left+1);
TreeNode root = new TreeNode(rootVal);
root.left = this.construct(preorder, inorder, left, inRootIdx-1, leftPreRootIdx);
root.right = this.construct(preorder, inorder, inRootIdx+1, right, rightPreRootIdx);
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) {
return this->Construct(preorder, inorder, 0, inorder.size()-1, 0);
}
private:
TreeNode* Construct(vector<int> &preorder, vector<int> &inorder, int left, int right, int pre_root_idx) {
if (left > right)
return NULL;
else if (left == right)
return new TreeNode(inorder[left]);
else {
int root_val = preorder[pre_root_idx];
int in_root_idx = 0;
for (int itr=left; itr<=right; ++itr) {
if (root_val == inorder[itr]) {
in_root_idx = itr;
break;
}
}
TreeNode *root = new TreeNode(root_val);
root->left = this->Construct(preorder, inorder, left, in_root_idx-1, pre_root_idx+1);
root->right = this->Construct(preorder, inorder, in_root_idx+1, right, pre_root_idx+(in_root_idx-left+1));
return root;
}
}
};