Posts tagged as “recursion”

花花酱 LeetCode 1376. Time Needed to Inform All Employees

By zxi on March 8, 2020

A company has n employees with a unique ID for each employee from 0 to n - 1. The head of the company has is the one with headID.

Each employee has one direct manager given in the manager array where manager[i] is the direct manager of the i-th employee, manager[headID] = -1. Also it’s guaranteed that the subordination relationships have a tree structure.

The head of the company wants to inform all the employees of the company of an urgent piece of news. He will inform his direct subordinates and they will inform their subordinates and so on until all employees know about the urgent news.

The i-th employee needs informTime[i] minutes to inform all of his direct subordinates (i.e After informTime[i] minutes, all his direct subordinates can start spreading the news).

Return the number of minutes needed to inform all the employees about the urgent news.

Example 1:

Input: n = 1, headID = 0, manager = [-1], informTime = [0]
Output: 0
Explanation: The head of the company is the only employee in the company.

Example 2:

Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
Output: 1
Explanation: The head of the company with id = 2 is the direct manager of all the employees in the company and needs 1 minute to inform them all.
The tree structure of the employees in the company is shown.

Example 3:

Input: n = 7, headID = 6, manager = [1,2,3,4,5,6,-1], informTime = [0,6,5,4,3,2,1]
Output: 21
Explanation: The head has id = 6. He will inform employee with id = 5 in 1 minute.
The employee with id = 5 will inform the employee with id = 4 in 2 minutes.
The employee with id = 4 will inform the employee with id = 3 in 3 minutes.
The employee with id = 3 will inform the employee with id = 2 in 4 minutes.
The employee with id = 2 will inform the employee with id = 1 in 5 minutes.
The employee with id = 1 will inform the employee with id = 0 in 6 minutes.
Needed time = 1 + 2 + 3 + 4 + 5 + 6 = 21.

Example 4:

Input: n = 15, headID = 0, manager = [-1,0,0,1,1,2,2,3,3,4,4,5,5,6,6], informTime = [1,1,1,1,1,1,1,0,0,0,0,0,0,0,0]
Output: 3
Explanation: The first minute the head will inform employees 1 and 2.
The second minute they will inform employees 3, 4, 5 and 6.
The third minute they will inform the rest of employees.

Example 5:

Input: n = 4, headID = 2, manager = [3,3,-1,2], informTime = [0,0,162,914]
Output: 1076

Constraints:

1 <= n <= 10^5
0 <= headID < n
manager.length == n
0 <= manager[i] < n
manager[headID] == -1
informTime.length == n
0 <= informTime[i] <= 1000
informTime[i] == 0 if employee i has no subordinates.
It is guaranteed that all the employees can be informed.

Solution 1: Build the graph + DFS

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

C++

// Author: Huahua

class Solution {

public:

int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {

vector<vector<int>> es(n);

for (int i = 0; i < n; ++i)

if (i != headID) es[manager[i]].push_back(i);

function<int(int)> dfs = [&](int cur) {

int t = 0;

for (int e : es[cur])

t = max(t, dfs(e));

return t + informTime[cur];

};

return dfs(headID);

}

};

Solution 2: Recursion with memoization

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

C++

// Author: Huahua

class Solution {

public:

int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {

vector<int> cache(n, -1);

function<int(int)> dfs = [&](int cur) {

if (cur == -1) return 0;

if (cache[cur] == -1)

cache[cur] = dfs(manager[cur]) + informTime[cur];

return cache[cur];

};

int ans = 0;

for (int i = 0; i < n; ++i)

ans = max(ans, dfs(i));

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:

cache = [-1] * n

def dfs(cur):

if cur == -1: return 0

if cache[cur] == -1:

cache[cur] = dfs(manager[cur]) + informTime[cur]

return cache[cur]

return max([dfs(i) for i in range(n)])

花花酱 LeetCode 1373. Maximum Sum BST in Binary Tree

By zxi on March 8, 2020

Given a binary tree root, the task is to return the maximum sum of all keys of any sub-tree which is also a Binary Search Tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.

Example 1:

Input: root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
Output: 20
Explanation: Maximum sum in a valid Binary search tree is obtained in root node with key equal to 3.

Example 2:

Input: root = [4,3,null,1,2]
Output: 2
Explanation: Maximum sum in a valid Binary search tree is obtained in a single root node with key equal to 2.

Example 3:

Input: root = [-4,-2,-5]
Output: 0
Explanation: All values are negatives. Return an empty BST.

Example 4:

Input: root = [2,1,3]
Output: 6

Example 5:

Input: root = [5,4,8,3,null,6,3]
Output: 7

Constraints:

Each tree has at most 40000 nodes..
Each node’s value is between [-4 * 10^4 , 4 * 10^4].

Solution: Recursion

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

C++

// Author: Huahua

class Solution {

public:

int maxSumBST(TreeNode* root) {

int ans = 0;

dfs(root, &ans);

return ans;

}

private:

// returns {lo, hi, sum, valid_bst}

tuple<int, int, int, bool> dfs(TreeNode* root, int* ans) {

if (!root) return {INT_MAX, INT_MIN, 0, true};

auto [ll, lh, ls, lv] = dfs(root->left, ans);

auto [rl, rh, rs, rv] = dfs(root->right, ans);

bool valid = lv && rv && root->val > lh && root->val < rl;

int sum = valid ? ls + rs + root->val : -1;

*ans = max(*ans, sum);

return {min(ll, root->val), max(rh, root->val), sum, valid};

}

};

Python3

# Author: Huahua

class Solution:

def maxSumBST(self, root: TreeNode) -> int:

# returns {lo, hi, sum, valid}

def dfs(node):

if not node: return (1e9, -1e9, 0, True)

ll, lh, ls, lv = dfs(node.left)

rl, rh, rs, rv = dfs(node.right)

v = lv and rv and node.val > lh and node.val < rl

s = ls + rs + node.val if v else -1

self.ans = max(self.ans, s)

return (min(ll, node.val), max(rh, node.val), s, v)

self.ans = 0

dfs(root)

return self.ans

花花酱 LeetCode 1372. Longest ZigZag Path in a Binary Tree

By zxi on March 8, 2020

Given a binary tree root, a ZigZag path for a binary tree is defined as follow:

Choose any node in the binary tree and a direction (right or left).
If the current direction is right then move to the right child of the current node otherwise move to the left child.
Change the direction from right to left or right to left.
Repeat the second and third step until you can’t move in the tree.

Zigzag length is defined as the number of nodes visited – 1. (A single node has a length of 0).

Return the longest ZigZag path contained in that tree.

Example 1:

Input: root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]
Output: 3
Explanation: Longest ZigZag path in blue nodes (right -> left -> right).

Example 2:

Input: root = [1,1,1,null,1,null,null,1,1,null,1]
Output: 4
Explanation: Longest ZigZag path in blue nodes (left -> right -> left -> right).

Example 3:

Input: root = [1]
Output: 0

Constraints:

Each tree has at most 50000 nodes..
Each node’s value is between [1, 100].

Solution: Recursion

For each node return
1. max ZigZag length if go left
2. max ZigZag length if go right
3. maz ZigZag length within the subtree

ZigZag(root):
ll, lr, lm = ZigZag(root.left)
rl, rr, rm = ZigZag(root.right)
return (lr+1, rl + 1, max(lr+1, rl+1, lm, rm))

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

C++

// Author: Huahua

class Solution {

public:

int longestZigZag(TreeNode* root) {

return get<2>(ZigZag(root));

}

// Returns {left, right, max}

tuple<int, int, int> ZigZag(TreeNode* root) {

if (!root) return {-1, -1, -1};

auto [ll, lr, lm] = ZigZag(root->left);

auto [rl, rr, rm] = ZigZag(root->right);

int l = lr + 1;

int r = rl + 1;

return {l, r, max({l, r, lm, rm})};

}

};

Python3

# Author: Huahua

class Solution:

def longestZigZag(self, root: TreeNode) -> int:

def ZigZag(node):

if not node: return (-1, -1, -1)

ll, lr, lm = ZigZag(node.left)

rl, rr, rm = ZigZag(node.right)

return (lr + 1, rl + 1, max(lr + 1, rl + 1, lm, rm))

return ZigZag(root)[2]

花花酱 LeetCode 1367. Linked List in Binary Tree

By zxi on March 1, 2020

Given a binary tree root and a linked list with head as the first node.

Return True if all the elements in the linked list starting from the head correspond to some downward path connected in the binary tree otherwise return False.

In this context downward path means a path that starts at some node and goes downwards.

Example 1:

Input: head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true
Explanation: Nodes in blue form a subpath in the binary Tree.

Example 2:

Input: head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true

Example 3:

Input: head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: false
Explanation: There is no path in the binary tree that contains all the elements of the linked list from head.

Constraints:

1 <= node.val <= 100 for each node in the linked list and binary tree.
The given linked list will contain between 1 and 100 nodes.
The given binary tree will contain between 1 and 2500 nodes.

Solution: Recursion

We need two recursion functions: isSubPath / isPath, the later one does a strict match.

Time complexity: O(|L| * |T|)
Space complexity: O(|T|)

C++

class Solution {

public:

bool isSubPath(ListNode* head, TreeNode* root) {

if (!root) return false;

return isPath(head, root) || isSubPath(head, root->left) || isSubPath(head, root->right);

}

private:

bool isPath(ListNode* head, TreeNode* root) {

if (!head) return true;

if (!root) return false;

if (root->val != head->val) return false;

return isPath(head->next, root->left) || isPath(head->next, root->right);

}

};

花花酱 LeetCode 1339. Maximum Product of Splitted Binary Tree

By zxi on February 1, 2020

Given a binary tree root. Split the binary tree into two subtrees by removing 1 edge such that the product of the sums of the subtrees are maximized.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: root = [1,2,3,4,5,6]
Output: 110
Explanation: Remove the red edge and get 2 binary trees with sum 11 and 10. Their product is 110 (11*10)

Example 2:

Input: root = [1,null,2,3,4,null,null,5,6]
Output: 90
Explanation:  Remove the red edge and get 2 binary trees with sum 15 and 6.Their product is 90 (15*6)

Example 3:

Input: root = [2,3,9,10,7,8,6,5,4,11,1]
Output: 1025

Example 4:

Input: root = [1,1]
Output: 1

Constraints:

Each tree has at most 50000 nodes and at least 2 nodes.
Each node’s value is between [1, 10000].

Solution: Recursion

Two passes:
First pass, compute the sum of the entire tree S.
Second pass, for each node, compute the sum of left/right subtree S_l, S_r.
ans = max{(S – S_l) * S_l, (S – S_r) * S_r}

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

C++

// Author: Huahua

class Solution {

public:

int maxProduct(TreeNode* root) {

const int kMod = 1e9 + 7;

long s = 0;

long ans = 0;

function<int(TreeNode*)> sum = [&](TreeNode* r) {

if (!r) return 0;

int sl = sum(r->left);

int sr = sum(r->right);

if (s) ans = max({ans, (s - sl) * sl, (s - sr) * sr});

return r->val + sl + sr;

};

s = sum(root);

sum(root);

return ans % kMod;

}

};