# 剑指 Offer 10- I. 斐波那契数列

F(0) = 0,   F(1) = 1
F(N) = F(N – 1) + F(N – 2), 其中 N > 1.

0 <= n <= 100

class Solution {
public:
int fib(int n) {
if(n == 0) return 0;
if(n == 1) return 1;
long long a = 0, b = 1;
for(int i = 2; i <= n; ++i) {
long long tmp = a + b;
tmp %= 1000000007;
a = b;
b = tmp;
}
return b;
}
};

typedef long long LL;

class Solution {
private:
vector<vector<LL>> multiply(vector<vector<LL>> &m1, vector<vector<LL>> &m2) {
int n = m1.size();
vector<vector<LL>> ans(n, vector<LL>(n, 0));
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
for(int k = 0; k < n; ++k) {
ans[i][j] += m1[i][k] * m2[k][j] % 1000000007;
}
}
}
return ans;
}
public:
int fib(int n) {
if(n == 0) return 0;
if(n == 1) return 1;

vector<vector<LL>> matrix = {{1,1},{1,0}};

vector<vector<LL>> ans = {{1,0},{0,1}};
while(n != 0) {
if(n % 2 == 1) ans = multiply(ans, matrix);
matrix = multiply(matrix, matrix);
n >>= 1;
}

return ans[0][1] % 1000000007;
}
};

# 剑指 Offer 07. 重建二叉树

3


/ \
9 20
/ \
15 7

0 <= 节点个数 <= 5000

class Solution {
private:
TreeNode* buildTree(vector<int>& preorder, int pl, int pr, vector<int>& inorder, int il, int ir, unordered_map<int,int> &hash) {
if(pr < pl || ir < il) return NULL;
TreeNode *root = new TreeNode(preorder[pl]);
int im = hash[preorder[pl]];
int len_left = im - il, len_right = ir - im;
root->left = buildTree(preorder, pl + 1, pl + len_left, inorder, il, im - 1, hash);
root->right = buildTree(preorder, pl + len_left + 1, pr, inorder, im + 1, ir, hash);
return root;
}
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
unordered_map<int,int> hash;
for(int i = 0; i < inorder.size(); ++i) hash[inorder[i]] = i;

int n = preorder.size();
return buildTree(preorder, 0, n - 1, inorder, 0, n - 1, hash);
}
};

# LeetCode Number of Good Leaf Nodes Pairs

5474. Number of Good Leaf Nodes Pairs

Given the root of a binary tree and an integer distance. A pair of two different leaf nodes of a binary tree is said to be good if the length of the shortest path between them is less than or equal to distance.

Return the number of good leaf node pairs in the tree.

Example 1:

Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.


Example 2:

Input: root = [1,2,3,4,5,6,7], distance = 3
Output: 2
Explanation: The good pairs are [4,5] and [6,7] with shortest path = 2. The pair [4,6] is not good because the length of ther shortest path between them is 4.


Example 3:

Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3
Output: 1
Explanation: The only good pair is [2,5].


Example 4:

Input: root = [100], distance = 1
Output: 0


Example 5:

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


Constraints:

• The number of nodes in the tree is in the range [1, 2^10].
• Each node’s value is between [1, 100].
• 1 <= distance <= 10

class Solution {
private:
void CollectLeaves(TreeNode *root, unordered_map<TreeNode*, vector<TreeNode*>> &all_paths, vector<TreeNode*> &one_path) {
if (root == NULL)return;
one_path.push_back(root);
if (root->left == NULL && root->right == NULL) {
all_paths[root] = one_path;
}
else {
CollectLeaves(root->left, all_paths, one_path);
CollectLeaves(root->right, all_paths, one_path);
}
one_path.pop_back();
}
int CalDist(vector<TreeNode*> &path1, vector<TreeNode*> &path2) {
int m = path1.size(), n = path2.size();
int i = 0;
while (i < m&&i < n) {
if (path1[i] != path2[i])break;
++i;
}
return (m - i) + (n - i);
}

public:
int countPairs(TreeNode* root, int distance) {
unordered_map<TreeNode*, vector<TreeNode*>> all_paths;
vector<TreeNode*> one_path;
CollectLeaves(root, all_paths, one_path);
vector<TreeNode*> leaves;
for (unordered_map<TreeNode*, vector<TreeNode*>>::iterator it = all_paths.begin(); it != all_paths.end(); ++it) {
leaves.push_back(it->first);
}

int ans = 0;
for (int i = 0; i < leaves.size(); ++i) {
for (int j = i + 1; j < leaves.size(); ++j) {
int d = CalDist(all_paths[leaves[i]], all_paths[leaves[j]]);
if (d <= distance)++ans;
}
}

return ans;
}
};

# LeetCode Number of Nodes in the Sub-Tree With the Same Label

5465. Number of Nodes in the Sub-Tree With the Same Label

Given a tree (i.e. a connected, undirected graph that has no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges. The root of the tree is the node 0, and each node of the tree has a label which is a lower-case character given in the string labels (i.e. The node with the number i has the label labels[i]).

The edges array is given on the form edges[i] = [ai, bi], which means there is an edge between nodes ai and bi in the tree.

Return an array of size n where ans[i] is the number of nodes in the subtree of the ith node which have the same label as node i.

A subtree of a tree T is the tree consisting of a node in T and all of its descendant nodes.

Example 1:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
Output: [2,1,1,1,1,1,1]
Explanation: Node 0 has label 'a' and its sub-tree has node 2 with label 'a' as well, thus the answer is 2. Notice that any node is part of its sub-tree.
Node 1 has a label 'b'. The sub-tree of node 1 contains nodes 1,4 and 5, as nodes 4 and 5 have different labels than node 1, the answer is just 1 (the node itself).


Example 2:

Input: n = 4, edges = [[0,1],[1,2],[0,3]], labels = "bbbb"
Output: [4,2,1,1]
Explanation: The sub-tree of node 2 contains only node 2, so the answer is 1.
The sub-tree of node 3 contains only node 3, so the answer is 1.
The sub-tree of node 1 contains nodes 1 and 2, both have label 'b', thus the answer is 2.
The sub-tree of node 0 contains nodes 0, 1, 2 and 3, all with label 'b', thus the answer is 4.


Example 3:

Input: n = 5, edges = [[0,1],[0,2],[1,3],[0,4]], labels = "aabab"
Output: [3,2,1,1,1]


Example 4:

Input: n = 6, edges = [[0,1],[0,2],[1,3],[3,4],[4,5]], labels = "cbabaa"
Output: [1,2,1,1,2,1]


Example 5:

Input: n = 7, edges = [[0,1],[1,2],[2,3],[3,4],[4,5],[5,6]], labels = "aaabaaa"
Output: [6,5,4,1,3,2,1]


Constraints:

• 1 <= n <= 10^5
• edges.length == n - 1
• edges[i].length == 2
• 0 <= ai, bi < n
• ai != bi
• labels.length == n
• labels is consisting of only of lower-case English letters.

class Solution {
private:
void DFS(int parid, int curid, vector<vector<int>> &children_string, unordered_map<int, vector<int>> &graph, const string &labels) {
int mylabel = labels[curid] - 'a';
++children_string[curid][mylabel];

for (int i = 0; i < graph[curid].size(); ++i) {
int childid = graph[curid][i];
if (childid == parid)continue;
DFS(curid, childid, children_string, graph, labels);
for (int j = 0; j < 26; ++j) {
children_string[curid][j] += children_string[childid][j];
}
}
}
public:
vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
unordered_map<int, vector<int>> graph;
for (int i = 0; i < edges.size(); ++i) {
graph[edges[i][0]].push_back(edges[i][1]);
graph[edges[i][1]].push_back(edges[i][0]);
}
vector<vector<int>> children_string(n, vector<int>(26, 0));

DFS(-1, 0, children_string, graph, labels);

vector<int> ans;
for (int i = 0; i < n; ++i) {
int mylabel = labels[i] - 'a';
ans.push_back(children_string[i][mylabel]);
}
return ans;
}
};


# LeetCode Binary Tree Maximum Path Sum

124. Binary Tree Maximum Path Sum

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:

Input: [1,2,3]

1
/ \
2   3

Output: 6


Example 2:

Input: [-10,9,20,null,null,15,7]

-10
/ \
9  20
/  \
15   7

Output: 42

• 仅包含节点本身（当左、右、父亲节点的路径和都是负数时）
• 穿过该节点，且还会往该节点的父亲上面走，说明最优路径的跟在该节点上面，该节点的左子树或右子树路径构成了最优路径的一部分
• 没有穿过该节点，即该节点为最优路径的跟，则路径的两端可能是该节点的左右孩子

class Solution {
public:
int maxSum(TreeNode *root, int &ans) {
if (root == NULL)return 0;
int left_sum = maxSum(root->left, ans), right_sum = maxSum(root->right, ans);

// 经过root节点的子树，还得往root的父亲上面走
int left_or_right_root = max(root->val, root->val + max(left_sum, right_sum));

// 最后一项是以root为根，左右子树都走，即不往root的父亲上面走
ans = max(ans, max(left_or_right_root, root->val + left_sum + right_sum));

return left_or_right_root;
}
int maxPathSum(TreeNode* root) {
int ans = INT_MIN;
maxSum(root, ans);
return ans;
}
};

# LeetCode Construct Binary Search Tree from Preorder Traversal

1008. Construct Binary Search Tree from Preorder Traversal

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. 1 <= preorder.length <= 100
2. The values of preorder are distinct.

class Solution {
public:
TreeNode* Work(vector<int> &preorder, int l, int r) {
if (l > r)return NULL;
if (l == r)return new TreeNode(preorder[l]);
TreeNode *root = new TreeNode(preorder[l]);
int mid = -1;
for (int i = l; i <= r; ++i) {
if (preorder[i] > root->val) {
mid = i;
break;
}
}
if (mid == -1)root->left = Work(preorder, l + 1, r);
else {
root->left = Work(preorder, l + 1, mid - 1);
root->right = Work(preorder, mid, r);
}
return root;
}
TreeNode* bstFromPreorder(vector<int>& preorder) {
return Work(preorder, 0, preorder.size() - 1);
}
};

# LeetCode Balance a Binary Search Tree

Given a binary search tree, return a balanced binary search tree with the same node values.

A binary search tree is balanced if and only if the depth of the two subtrees of every node never differ by more than 1.

If there is more than one answer, return any of them.

Example 1:

Input: root = [1,null,2,null,3,null,4,null,null]
Output: [2,1,3,null,null,null,4]
Explanation: This is not the only correct answer, [3,1,4,null,2,null,null] is also correct.


Constraints:

• The number of nodes in the tree is between 1 and 10^4.
• The tree nodes will have distinct values between 1 and 10^5.

class Solution {
public:
void preIter(TreeNode* root, vector<int> &nums) {
if (root == NULL)return;
preIter(root->left, nums);
nums.push_back(root->val);
preIter(root->right, nums);
}
TreeNode* constructBST(vector<int> &nums, int l, int r) {
if (l > r)return NULL;
if (l == r)return new TreeNode(nums[l]);

int mid = l + (r - l) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = constructBST(nums, l, mid - 1);
root->right = constructBST(nums, mid + 1, r);
return root;
}
TreeNode* balanceBST(TreeNode* root) {
vector<int> nums;
preIter(root, nums);
int n = nums.size();
return constructBST(nums, 0, n - 1);
}
};

# LeetCode Time Needed to Inform All Employees

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.

class Solution {
public:
int maxTime(int headID, map<int, vector<int>>& employees, vector<int>& informTime) {

int child_max = 0;
for (int i = 0; i < employees[headID].size(); ++i) {
int cur_child = maxTime(employees[headID][i], employees, informTime);
child_max = max(child_max, cur_child);
}
return cur_time + child_max;
}
int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
if (n == 1)return informTime[0];
map<int, vector<int>> employees;
for (int i = 0; i < n; ++i) {
employees[manager[i]].push_back(i);
}
}
};

# LeetCode Print Binary Tree

Print a binary tree in an m*n 2D string array following these rules:

1. The row number m should be equal to the height of the given binary tree.
2. The column number n should always be an odd number.
3. The root node’s value (in string format) should be put in the exactly middle of the first row it can be put. The column and the row where the root node belongs will separate the rest space into two parts (left-bottom part and right-bottom part). You should print the left subtree in the left-bottom part and print the right subtree in the right-bottom part. The left-bottom part and the right-bottom part should have the same size. Even if one subtree is none while the other is not, you don’t need to print anything for the none subtree but still need to leave the space as large as that for the other subtree. However, if two subtrees are none, then you don’t need to leave space for both of them.
4. Each unused space should contain an empty string "".
5. Print the subtrees following the same rules.

Example 1:

Input:
1
/
2
Output:
[["", "1", ""],
["2", "", ""]]


Example 2:

Input:
1
/ \
2   3
\
4
Output:
[["", "", "", "1", "", "", ""],
["", "2", "", "", "", "3", ""],
["", "", "4", "", "", "", ""]]


Example 3:

Input:
1
/ \
2   5
/
3
/
4
Output:

[["",  "",  "", "",  "", "", "", "1", "",  "",  "",  "",  "", "", ""]
["",  "",  "", "2", "", "", "", "",  "",  "",  "",  "5", "", "", ""]
["",  "3", "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]
["4", "",  "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]]


Note: The height of binary tree is in the range of [1, 10].

class Solution {
public:
int height(TreeNode* root) {
if (root == NULL)return 0;
if (root->left == NULL && root->right == NULL)return 1;
int lh = height(root->left), rh = height(root->right);
return (lh > rh ? lh : rh) + 1;
}
void work(TreeNode* root, vector<vector<string>>& strTree,int layer,int left,int right) {
if (root == NULL)return;
int mid = (left + right) / 2;
strTree[layer][mid] = to_string(root->val);
work(root->left, strTree, layer + 1, left, mid - 1);
work(root->right, strTree, layer + 1, mid + 1, right);
}
vector<vector<string>> printTree(TreeNode* root) {
int h = height(root);
vector<vector<string>> strTree(h, vector<string>((1 << h) - 1, ""));
work(root, strTree, 0, 0, strTree[0].size() - 1);
return strTree;
}
};

# LeetCode Search in a Binary Search Tree

700. Search in a Binary Search Tree

Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node’s value equals the given value. Return the subtree rooted with that node. If such node doesn’t exist, you should return NULL.

For example,

Given the tree:
4
/ \
2   7
/ \
1   3

And the value to search: 2


You should return this subtree:

      2
/ \
1   3


In the example above, if we want to search the value 5, since there is no node with value 5, we should return NULL.

Note that an empty tree is represented by NULL, therefore you would see the expected output (serialized tree format) as [], not null.

class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
if (root == NULL)return NULL;
if (root->val == val)return root;
if (val < root->val)return searchBST(root->left, val);
else return searchBST(root->right, val);
}
};