花花酱 LeetCode 889. Construct Binary Tree from Preorder and Postorder Traversal

By zxi on August 23, 2018

Problem

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[] and post[] are both permutations of 1, 2, ..., pre.length.
It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.

Solution: Recursion

pre = [(root) (left-child) (right-child)]

post = [(left-child) (right-child) (root)]

We need to recursively find the first node in pre.left-child from post.left-child

e.g.

pre = [(1), (2,4,5), (3,6,7)]

post = [(4,5,2), (6,7,3), (1)]

First element of left-child is 2 and the length of it is 3.

root = new TreeNode(1)
root.left = build((2,4,5), (4,5,2))
root.right = build((3,6,7), (6,7,3))

Time complexity: O(n^2)

Space complexity: O(n)

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {

return constructFromPrePost(cbegin(pre), cend(pre), cbegin(post), cend(post));

}

private:

typedef vector<int>::const_iterator VIT;

TreeNode* constructFromPrePost(VIT pre_l, VIT pre_r, VIT post_l, VIT post_r) {

if (pre_l == pre_r) return nullptr;

TreeNode* root = new TreeNode(*pre_l);

++pre_l;

--post_r;

if (pre_l == pre_r) return root;

VIT post_m = next(find(post_l, post_r, *pre_l));

VIT pre_m = pre_l + (post_m - post_l);

root->left = constructFromPrePost(pre_l, pre_m, post_l, post_m);

root->right = constructFromPrePost(pre_m, pre_r, post_m, post_r);

return root;

}

};

Time complexity: O(n^2)

Space complexity: O(n)

"""

Author: Huahua

Running time: 60 ms

"""

class Solution:

def constructFromPrePost(self, pre, post):

def build(i, j, n):

if n <= 0: return None

root = TreeNode(pre[i])

if n == 1: return root

k = j

while post[k] != pre[i + 1]: k += 1

l = k - j + 1

root.left = build(i + 1, j, l)

root.right = build(i + l + 1, k + 1, n - l - 1)

return root

return build(0, 0, len(pre))

Time complexity: O(n)

"""

Author: Huahua

Running time: 52 ms (beats 100%)

"""

class Solution:

def constructFromPrePost(self, pre, post):

def build(i, j, n):

if n <= 0: return None

root = TreeNode(pre[i])

if n == 1: return root

k = index[pre[i + 1]]

l = k - j + 1

root.left = build(i + 1, j, l)

root.right = build(i + l + 1, k + 1, n - l - 1)

return root

index = {}

for i in range(len(pre)):

index[post[i]] = i

return build(0, 0, len(pre))

花花酱 LeetCode 589. N-ary Tree Preorder Traversal

By zxi on July 12, 2018

Problem

Given an n-ary tree, return the preorder traversal of its nodes’ values.

For example, given a 3-ary tree:

Return its preorder traversal as: [1,3,5,6,2,4].

Note: Recursive solution is trivial, could you do it iteratively?

Solution1: Recursive

// Author: Huahua

// Running time: 48 ms

class Solution {

public:

vector<int> preorder(Node* root) {

vector<int> ans;

preorder(root, ans);

return ans;

}

private:

void preorder(Node* root, vector<int>& ans) {

if (!root) return;

ans.push_back(root->val);

for (const auto& child : root->children)

preorder(child, ans);

}

};

Solution2: Iterative

// Author: Huahua

// Running time: 52 ms

class Solution {

public:

vector<int> preorder(Node* root) {

if (!root) return {};

vector<int> ans;

stack<Node*> s;

s.push(root);

while (!s.empty()) {

const Node* node = s.top(); s.pop();

ans.push_back(node->val);

for (auto it = node->children.rbegin(); it != node->children.rend(); ++it)

s.push(*it);

}

return ans;

}

};

Problem:

Given a binary tree, return the postorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

Solution 1:

// Author: Huahua

class Solution {

public:

vector<int> postorderTraversal(TreeNode* root) {

vector<int> ans;

postorderTraversal(root, ans);

return ans;

}

void postorderTraversal(TreeNode* root, vector<int>& ans) {

if (!root) return;

postorderTraversal(root->left, ans);

postorderTraversal(root->right, ans);

ans.push_back(root->val);

}

};

Solution 2:

// Author: Huahua

class Solution {

public:

vector<int> postorderTraversal(TreeNode* root) {

if (!root) return {};

vector<int> ans;

const vector<int> l = postorderTraversal(root->left);

const vector<int> r = postorderTraversal(root->right);

ans.insert(ans.end(), l.begin(), l.end());

ans.insert(ans.end(), r.begin(), r.end());

ans.push_back(root->val);

return ans;

}

};

Solution 3:

// Author: Huahua

class Solution {

public:

vector<int> postorderTraversal(TreeNode* root) {

if (!root) return {};

deque<int> ans;

stack<TreeNode*> s;

s.push(root);

while (!s.empty()) {

TreeNode* n = s.top();

s.pop();

ans.push_front(n->val); // O(1)

if (n->left) s.push(n->left);

if (n->right) s.push(n->right);

}

return vector<int>(ans.begin(), ans.end());

}

};

Posts tagged as “preorder”

花花酱 LeetCode 889. Construct Binary Tree from Preorder and Postorder Traversal

Problem

Solution: Recursion

花花酱 LeetCode 589. N-ary Tree Preorder Traversal

Problem

Solution1: Recursive

Solution2: Iterative

Related Problems

花花酱 LeetCode 145. Binary Tree Postorder Traversal

Problem:

Solution 1:

Solution 2:

Solution 3: