原题
Return any binary tree that matches the given preorder and postorder traversals.
Values in the traversals pre
and post
are distinct positive integers.
Example 1:
Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1] Output: [1,2,3,4,5,6,7]
Note:
1 <= pre.length == post.length <= 30
pre[]
andpost[]
are both permutations of1, 2, ..., pre.length
.- It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.
题解
考察构造二叉树,其需要同时满足输入的先序遍历和后序遍历。并输出任意一个满足要求的解。为什么说要输出任意一个满足的解,因为在这种情况下,会有两种解:
pre = [1, 2, 4] post = [4, 2, 1]
第一种情况
1 2 4
第二种情况
1 2 4
以上两种情况都是满足原题要求的,所以当一个节点只有一个子节点时,默认地认为它是该节点的左子节点,即第一种情况的解。
递归 & 分治策略
pre (root) (left) (right) 1, 2,4,5, 3,6,7 post (left) (right) (root) 4,5,2, 6,7,3, 1
分析原题的pre和post向量可知,pre[0]是root,假设map m。m->first代表每一个节点的值(val),m->second代表其所属的索引。则可知道post[pre[1]] + 1就是当前root的左节点的所有元素个数(长度)。同理,可以容易推出右节点的所有元素的个数。
那么利用分治策略,将一个大规模的问题分解成两个更小规模的问题,不断的递归下去,直到逼近边界条件,当可以容易求出解时返回。
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution
{
public:
TreeNode *constructFromPrePost(vector<int> &pre, vector<int> &post)
{
int len = post.size();
// traversing the post
for (int i = 0; i < len; i++)
{
m[post[i]] = i;
}
return construct(pre, post, 0, len – 1, 0, len – 1);
}
TreeNode *construct(vector<int> &pre, vector<int> &post, int pre_s, int pre_e, int post_s, int post_e)
{
// boundary conditions
if (pre_s > pre_e)
return nullptr;
TreeNode *root = new TreeNode(pre[pre_s]);
if (pre_s == pre_e)
return root;
// get left & right node
int left_len = m[pre[pre_s + 1]] – post_s + 1;
root->left = construct(pre, post, pre_s + 1, pre_s + left_len, post_s, post_s + left_len – 1);
root->right = construct(pre, post, pre_s + left_len + 1, pre_e, post_s + left_len, post_e – 1);
return root;
}
private:
map<int, int> m;
};
复杂度分析
Time Complexity: O(n) ~ O(n^2)
当树是一个理想状态(满二叉树)时,他的递归深度f(n) = log(n+1)/2 = O(logn),此时递归公式为:T(n) = aT(n/b) + O(1) = 2T(n/2) + O(1),根据主定理可知,T(n) = O(n)
当树是一个最差状态时,即每个节点最多只有一个做节点,他的递归深度f(n) = O(n)
Space Complexity: O(logn) ~ O(n)
*迭代 & stack
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution
{
public:
TreeNode *constructFromPrePost(vector<int> pre, vector<int> post)
{
vector<TreeNode *> s;
s.push_back(new TreeNode(pre[0]));
for (int i = 1, j = 0; i < pre.size(); ++i)
{
TreeNode *node = new TreeNode(pre[i]);
while (s.back()->val == post[j])
s.pop_back(), j++;
if (s.back()->left == NULL)
s.back()->left = node;
else
s.back()->right = node;
s.push_back(node);
}
return s[0];
}
};
复杂度分析
Time Complexity: O(n)
Space Complexity: O(n)
原题:https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/description/
Github 源码:
递归 & 分治策略
参考:
递归公式主定理:https://blog.csdn.net/ycf74514/article/details/48813289
算法分析渐进符号:https://blog.csdn.net/gaoxiangnumber1/article/details/45066841
文章来源:胡小旭 => [LeetCode 889]Construct Binary Tree from Preorder and Postorder Traversal