花花酱 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) + ")";

}

};

花花酱 LeetCode 633. Sum of Square Numbers

By zxi on August 22, 2018

Problem

Given a non-negative integer c, your task is to decide whether there’re two integers a and b such that a² + b² = c.

Example 1:

Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5

Example 2:

Input: 3
Output: False

Solution: Math

Time complexity: O(sqrt(c))

Space complexity: O(1)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

bool judgeSquareSum(int c) {

int m = sqrt(c);

for (int a = 0; a <= m; ++a) {

int b = round(sqrt(c - a * a));

if (a * a + b * b == c) return true;

}

return false;

}

};

花花酱 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

花花酱 LeetCode 633. Sum of Square Numbers

Problem

Solution: Math

Huahua's Tech Road

花花酱 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

花花酱 LeetCode 633. Sum of Square Numbers

Problem

Solution: Math