construct Archives - Huahua's Tech Road

花花酱 LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal

By zxi on October 3, 2019

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:

Solution: Recursion

Preprocessing: use a hashtable to store the index of element in preorder array.

For an element in inorder array, find the pos of it in preorder array in O(1), anything to the left will be the leftchild and anything to the right will be the right child.

e.g.
buildTree([9, 3, 15, 20, 7], [3, 9, 20, 15, 7]):
root = TreeNode(9) # inorder[0] = 9
root.left = buildTree([3], [3])
root.right = buildTree([15, 20, 7], [20, 15, 7])
return root

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {

unordered_map<int, int> pos;

for (int i = 0; i < inorder.size(); i++)

pos[inorder[i]] = i;

function<TreeNode*(int, int, int, int)> buildTree = [&](int is, int ie, int ps, int pe) {

if (ps > pe) return (TreeNode*)nullptr;

int im = pos[preorder[ps]];

int pm = ps + (im - is);

auto root = new TreeNode(preorder[ps]);

root->left = buildTree(is, im - 1, ps + 1, pm);

root->right = buildTree(im + 1, ie, pm + 1, pe);

return root;

};

return buildTree(0, inorder.size() - 1, 0, preorder.size() - 1);

}

};

花花酱 LeetCode 1008. Construct Binary Search Tree from Preorder Traversal

By zxi on March 9, 2019

Return the root node of a binary search tree that matches the given preorder traversal.

(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val. Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)

Example 1:

Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

Note:

1 <= preorder.length <= 100
The values of preorder are distinct.

Solution: Recursion

Time complexity: O(n^2)
Space complexity: O(n)

C++

// Author: Huahua, 8 ms, 10.8 MB

class Solution {

public:

TreeNode* bstFromPreorder(vector<int>& preorder) {

return build(preorder, 0, preorder.size());

}

private:

TreeNode* build(const vector<int>& preorder, int s, int e) {

if (s >= e) return nullptr;

auto root = new TreeNode(preorder[s]);

int m = s;

while (m < e && preorder[m] <= root->val) ++m;

root->left = build(preorder, s + 1, m);

root->right = build(preorder, m, e);

return root;

}

};

C++/iterator

class Solution {

public:

TreeNode* bstFromPreorder(vector<int>& preorder) {

return build(begin(preorder), end(preorder));

}

private:

typedef vector<int>::const_iterator IT;

TreeNode* build(IT s, IT e) {

if (s >= e) return nullptr;

auto root = new TreeNode(*s);

IT m = s;

while (m < e && *m <= *s) ++m;

root->left = build(s + 1, m);

root->right = build(m, e);

return root;

}

};

花花酱 LeetCode 984. String Without AAA or BBB

By zxi on January 27, 2019

Given two integers A and B, return any string S such that:

S has length A + B and contains exactly A 'a' letters, and exactly B 'b' letters;
The substring 'aaa' does not occur in S;
The substring 'bbb' does not occur in S.

Example 1:

Input: A = 1, B = 2
Output: "abb"
Explanation: "abb", "bab" and "bba" are all correct answers.

Example 2:

Input: A = 4, B = 1
Output: "aabaa"

Note:

0 <= A <= 100
0 <= B <= 100
It is guaranteed such an S exists for the given A and B.

C++

class Solution {

public:

string strWithout3a3b(int A, int B) {

char a = 'a';

char b = 'b';

if (B > A) {

swap(A, B);

swap(a, b);

}

string ans;

while (A || B) {

if (A > 0) { ans += a; --A; }

if (A > B) { ans += a; --A; }

if (B > 0) { ans += b; --B; }

}

return ans;

}

};

C++ / overload

class Solution {

public:

string strWithout3a3b(int A, int B, char a = 'a', char b = 'b') {

if (B > A) return strWithout3a3b(B, A, b, a);

string ans;

while (A || B) {

if (A > 0) { ans += a; --A; }

if (A > B) { ans += a; --A; }

if (B > 0) { ans += b; --B; }

}

return ans;

}

};

Posts tagged as “construct”

花花酱 LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal

Solution: Recursion

C++

Related Problems

花花酱 LeetCode 1008. Construct Binary Search Tree from Preorder Traversal

Solution: Recursion

C++

C++/iterator

花花酱 LeetCode 984. String Without AAA or BBB

C++

C++ / overload