Huahua’s Tech Road

花花酱 LeetCode 235. Lowest Common Ancestor of a Binary Search Tree

By zxi on January 29, 2020

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given binary search tree: root = [6,2,8,0,4,7,9,null,null,3,5]

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Note:

All of the nodes’ values will be unique.
p and q are different and both values will exist in the BST.

Solution: Recursion

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

C++

// Author: Huahua

class Solution {

public:

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

if (p->val < root->val && q->val < root->val)

return lowestCommonAncestor(root->left, p, q);

if (p->val > root->val && q->val > root->val)

return lowestCommonAncestor(root->right, p, q);

return root;

}

};

花花酱 LeetCode 257. Binary Tree Paths

By zxi on January 29, 2020

Given a binary tree, return all root-to-leaf paths.

Note: A leaf is a node with no children.

Example:

Input:

   1
 /   \
2     3
 \
  5

Output: ["1->2->5", "1->3"]

Explanation: All root-to-leaf paths are: 1->2->5, 1->3

Solution: Recursion

Time complexity: O(n)
Space complexity: O(n) / output can be O(n^2)

C++

// Author: Huahua

class Solution {

public:

vector<string> binaryTreePaths(TreeNode* root) {

vector<string> ans;

string s;

function<void(TreeNode*, int)> preorder = [&](TreeNode* node, int l) {

if (!node) return;

s += (l > 0 ? "->" : "") + to_string(node->val);

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

ans.push_back(s);

preorder(node->left, s.size());

preorder(node->right, s.size());

while (s.size() != l) s.pop_back();

};

preorder(root, 0);

return ans;

}

};

花花酱 LeetCode 107. Binary Tree Level Order Traversal II

By zxi on January 29, 2020

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree [3,9,20,null,null,15,7],

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

Solution: Recursion

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

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> levelOrderBottom(TreeNode *root) {

vector<vector<int>> ans;

levelOrderBottom(root, 0, ans);

reverse(ans.begin(), ans.end());

return ans;

}

private:

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

if (!root) return;

while (ans.size() <= depth) ans.push_back({});

ans[depth].push_back(root->val);

levelOrderBottom(root->left, depth + 1, ans);

levelOrderBottom(root->right, depth + 1, ans);

}

};

花花酱 LeetCode 144. Binary Tree Preorder Traversal

By zxi on January 29, 2020

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

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,2,3]

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

Solution 1: Recursion

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

C++

// Author: Huahua

class Solution {

public:

vector<int> preorderTraversal(TreeNode* root) {

vector<int> ans;

function<void(TreeNode*)> preorder = [&](TreeNode* n) {

if (!n) return;

ans.push_back(n->val);

preorder(n->left);

preorder(n->right);

};

preorder(root);

return ans;

}

};

Solution 2: Stack

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

C++

// Author: Huahua

class Solution {

public:

vector<int> preorderTraversal(TreeNode* root) {

vector<int> ans;

stack<TreeNode*> s;

if (root) s.push(root);

while (!s.empty()) {

TreeNode* n = s.top();

ans.push_back(n->val);

s.pop();

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

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

}

return ans;

}

花花酱 LeetCode 1335. Minimum Difficulty of a Job Schedule

By zxi on January 27, 2020

You want to schedule a list of jobs in d days. Jobs are dependent (i.e To work on the i-th job, you have to finish all the jobs j where 0 <= j < i).

You have to finish at least one task every day. The difficulty of a job schedule is the sum of difficulties of each day of the d days. The difficulty of a day is the maximum difficulty of a job done in that day.

Given an array of integers jobDifficulty and an integer d. The difficulty of the i-th job is jobDifficulty[i].

Return the minimum difficulty of a job schedule. If you cannot find a schedule for the jobs return -1.

Example 1:

Input: jobDifficulty = [6,5,4,3,2,1], d = 2
Output: 7
Explanation: First day you can finish the first 5 jobs, total difficulty = 6.
Second day you can finish the last job, total difficulty = 1.
The difficulty of the schedule = 6 + 1 = 7

Example 2:

Input: jobDifficulty = [9,9,9], d = 4
Output: -1
Explanation: If you finish a job per day you will still have a free day. you cannot find a schedule for the given jobs.

Example 3:

Input: jobDifficulty = [1,1,1], d = 3
Output: 3
Explanation: The schedule is one job per day. total difficulty will be 3.

Example 4:

Input: jobDifficulty = [7,1,7,1,7,1], d = 3
Output: 15

Example 5:

Input: jobDifficulty = [11,111,22,222,33,333,44,444], d = 6
Output: 843

Constraints:

1 <= jobDifficulty.length <= 300
0 <= jobDifficulty[i] <= 1000
1 <= d <= 10

Solution: DP

dp[i][k] := min difficulties to schedule jobs 1~i in k days.

Schedule 1 ~ j in k – 1 days and schedule j + 1 ~ i in 1 day.

Init: dp[0][0] = 0
Transition: dp[i][k] := min(dp[j][k -1] + max(jobs[j + 1 ~ i]), k – 1 <= j < i
Answer: dp[n][d]

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

C++

// Author: Huahua

class Solution {

public:

int minDifficulty(vector<int>& jobs, int d) {

const int n = jobs.size();

if (d > n) return -1;

vector<vector<int>> dp(n + 1, vector<int>(d + 1, INT_MAX / 2));

dp[0][0] = 0;

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

for (int j = i - 1, md = 0; j >= 0; --j) {

md = max(md, jobs[j]);

for (int k = 1; k <= min(i, d); ++k)

dp[i][k] = min(dp[i][k], dp[j][k - 1] + md);

}

return dp[n][d];

}

};

Huahua's Tech Road

花花酱 LeetCode 235. Lowest Common Ancestor of a Binary Search Tree

Solution: Recursion

C++

花花酱 LeetCode 257. Binary Tree Paths

Solution: Recursion

C++

花花酱 LeetCode 107. Binary Tree Level Order Traversal II

Solution: Recursion

C++

Related Problems

花花酱 LeetCode 144. Binary Tree Preorder Traversal

Solution 1: Recursion

C++

Solution 2: Stack

C++

花花酱 LeetCode 1335. Minimum Difficulty of a Job Schedule

Solution: DP

C++