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