Posts published in August 2018

花花酱 LeetCode 894. All Possible Full Binary Trees

By zxi on August 26, 2018

Problem

A full binary tree is a binary tree where each node has exactly 0 or 2 children.

Return a list of all possible full binary trees with N nodes. Each element of the answer is the root node of one possible tree.

Each node of each tree in the answer must have node.val = 0.

You may return the final list of trees in any order.

Example 1:

Input: 7
Output: [[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]
Explanation:

Note:

1 <= N <= 20

Solution: Recursion

Key observations:

n must be odd, If n is even, no possible trees
ans is the cartesian product of trees(i) and trees(n-i-1). Ans = {Tree(0, l, r) for l, r in trees(i) X trees(N – i – 1)}.

w/o cache

C++

// Author: Huahua

// Running time: 72 ms

class Solution {

public:

vector<TreeNode*> allPossibleFBT(int N) {

if (N % 2 == 0) return {};

if (N == 1) return {new TreeNode(0)};

vector<TreeNode*> ans;

for (int i = 1; i < N; i += 2) {

for (const auto& l : allPossibleFBT(i))

for (const auto& r : allPossibleFBT(N - i - 1)) {

auto root = new TreeNode(0);

root->left = l;

root->right = r;

ans.push_back(root);

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 20 ms

class Solution {

public List<TreeNode> allPossibleFBT(int N) {

List<TreeNode> ans = new ArrayList<>();

if (N % 2 == 0) return ans;

if (N == 1) {

ans.add(new TreeNode(0));

return ans;

}

for (int i = 1; i < N; i += 2) {

for (TreeNode l : allPossibleFBT(i))

for (TreeNode r : allPossibleFBT(N - i - 1)) {

TreeNode root = new TreeNode(0);

root.left = l;

root.right = r;

ans.add(root);

}

return ans;

}

Python

"""

Author: Huahua

Running time: 396 ms

"""

class Solution:

def allPossibleFBT(self, N):

if N % 2 == 0: return []

if N == 1: return [TreeNode(0)]

ans = []

for i in range(1, N, 2):

for l in self.allPossibleFBT(i):

for r in self.allPossibleFBT(N - i - 1):

root = TreeNode(0)

root.left = l

root.right = r

ans.append(root)

return ans

w/cache

C++

// Author: Huahua

// Running time: 68 ms

static constexpr int kMaxN = 20 + 1;

static array<vector<TreeNode*>, kMaxN> m;

class Solution {

public:

vector<TreeNode*> allPossibleFBT(int N) {

return trees(N);

}

private:

vector<TreeNode*>& trees(int N) {

if (m[N].size() > 0) return m[N];

vector<TreeNode*>& ans = m[N];

if (N % 2 == 0) return ans = {};

if (N == 1) ans = {new TreeNode(0)};

for (int i = 1; i < N; i += 2) {

for (const auto& l : trees(i))

for (const auto& r : trees(N - i - 1)) {

auto root = new TreeNode(0);

root->left = l;

root->right = r;

ans.push_back(root);

}

return ans;

}

};

Python

using itertools.product w/ cache

"""

Author: Huahua

Running time: 188 ms

"""

m = [[] for _ in range(21)]

class Solution:

def allPossibleFBT(self, N):

if N % 2 == 0: return []

if N == 1: return [TreeNode(0)]

if len(m[N]) > 0: return m[N]

ans = []

for i in range(1, N, 2):

for l, r in itertools.product(self.allPossibleFBT(i),

self.allPossibleFBT(N - i - 1)):

root = TreeNode(0)

root.left = l

root.right = r

ans.append(root)

m[N] = ans

return ans

C++

// Author: Huahua

// Running time: 100 ms

class Solution {

public:

vector<TreeNode*> allPossibleFBT(int N) {

if (N % 2 == 0) return {};

vector<vector<TreeNode*>> dp(N + 1);

dp[1] = {new TreeNode(0)};

for (int i = 3; i <= N; i += 2)

for (int j = 1; j < i; j += 2) {

int k = i - j - 1;

for (const auto& l : dp[j])

for (const auto& r : dp[k]) {

auto root = new TreeNode(0);

root->left = l;

root->right = r;

dp[i].push_back(root);

}

return dp[N];

}

};

Benchmark

No-cache vs cached

C++

#include <iostream>

#include <vector>

#include <array>

#include <ctime>

#include <cstdio>

using namespace std;

struct TreeNode {

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

static constexpr int kMaxN = 101 + 1;

static array<vector<TreeNode*>, kMaxN> m;

class NoCache {

public:

vector<TreeNode*> allPossibleFBT(int N) {

if (N % 2 == 0) return {};

if (N == 1) return {new TreeNode(0)};

vector<TreeNode*> ans;

for (int i = 1; i < N; i += 2) {

for (const auto& l : allPossibleFBT(i))

for (const auto& r : allPossibleFBT(N - i - 1)) {

auto root = new TreeNode(0);

root->left = l;

root->right = r;

ans.push_back(root);

}

return ans;

}

};

class Cached {

public:

vector<TreeNode*> allPossibleFBT(int N) {

return trees(N);

}

private:

vector<TreeNode*>& trees(int N) {

if (m[N].size() > 0) return m[N];

vector<TreeNode*>& ans = m[N];

if (N % 2 == 0) return ans = {};

if (N == 1) ans = {new TreeNode(0)};

for (int i = 1; i < N; i += 2) {

for (const auto& l : trees(i))

for (const auto& r : trees(N - i - 1)) {

auto root = new TreeNode(0);

root->left = l;

root->right = r;

ans.push_back(root);

}

return ans;

}

};

int main(int argc, char** argv) {

printf("N\tno-cache\tcached\n");

for (int i = 1; i <= 35; i += 2) {

printf("%02d\t", i);

{

auto start = clock();

(void)(NoCache().allPossibleFBT(i));

printf("%8.4f\t", static_cast<double>(clock() - start) / CLOCKS_PER_SEC);

}

{

// Clear the cache.

for (int j = 0; j < kMaxN; ++j)

m[i].clear();

auto start = clock();

(void)(Cached().allPossibleFBT(i));

printf("%8.4f\n", static_cast<double>(clock() - start) / CLOCKS_PER_SEC);

}

return 0;

}

花花酱 LeetCode 112. Path Sum

By zxi on August 25, 2018

Problem

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Solution: Recursion

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

bool hasPathSum(TreeNode* root, int sum) {

if (!root) return false;

if (!root->left && !root->right) return root->val==sum;

int new_sum = sum - root->val;

return hasPathSum(root->left, new_sum) || hasPathSum(root->right, new_sum);

}

};

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 606. Construct String from Binary Tree

By zxi on August 22, 2018

Problem

You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way.

The null node needs to be represented by empty parenthesis pair “()”. And you need to omit all the empty parenthesis pairs that don’t affect the one-to-one mapping relationship between the string and the original binary tree.

Example 1:

Input: Binary tree: [1,2,3,4]
       1
     /   \
    2     3
   /    
  4     

Output: "1(2(4))(3)"

Explanation: Originallay it needs to be "1(2(4)())(3()())", 
but you need to omit all the unnecessary empty parenthesis pairs. 
And it will be "1(2(4))(3)".

Example 2:

Input: Binary tree: [1,2,3,null,4]
       1
     /   \
    2     3
     \  
      4 

Output: "1(2()(4))(3)"

Explanation: Almost the same as the first example, 
except we can't omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.

Solution: Recursion

Time complexity: O(n^2)

space complexity: O(n^2)

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

string tree2str(TreeNode* t) {

if (!t) return "";

const string s = std::to_string(t->val);

// case 0: s

if (!t->left && !t->right)

return s;

// case 1: s(l)

if (!t->right)

return s + "(" + tree2str(t->left) + ")";

// general: s(l)(r)

return s + "(" + tree2str(t->left) + ")" + "(" + tree2str(t->right) + ")";

}

};

Posts published in August 2018

花花酱 LeetCode 894. All Possible Full Binary Trees

Problem

Solution: Recursion

C++

Java

Python

C++

Python

C++

Benchmark

C++

花花酱 LeetCode 112. Path Sum

Problem

Solution: Recursion

Related Problems

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

Problem

Solution: Recursion

花花酱 LeetCode 606. Construct String from Binary Tree

Problem

Solution: Recursion

Posts published in August 2018

花花酱 LeetCode 894. All Possible Full Binary Trees

Problem

Solution: Recursion

C++

Java

Python

C++

Python

C++

Benchmark

C++

花花酱 LeetCode 112. Path Sum

Problem

Solution: Recursion

Related Problems

花花酱 LeetCode 141. Linked List Cycle

Problem

Solution1: HashTable

Solution2: Fast + Slow pointers

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

Problem

Solution: Recursion

花花酱 LeetCode 606. Construct String from Binary Tree

Problem

Solution: Recursion