# 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 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 Frog Position After T Seconds

1377. Frog Position After T Seconds

Given an undirected tree consisting of n vertices numbered from 1 to n. A frog starts jumping from the vertex 1. In one second, the frog jumps from its current vertex to another unvisited vertex if they are directly connected. The frog can not jump back to a visited vertex. In case the frog can jump to several vertices it jumps randomly to one of them with the same probability, otherwise, when the frog can not jump to any unvisited vertex it jumps forever on the same vertex.

The edges of the undirected tree are given in the array edges, where edges[i] = [fromi, toi] means that exists an edge connecting directly the vertices fromi and toi.

Return the probability that after t seconds the frog is on the vertex target.

Example 1:

Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4
Output: 0.16666666666666666
Explanation: The figure above shows the given graph. The frog starts at vertex 1, jumping with 1/3 probability to the vertex 2 after second 1 and then jumping with 1/2 probability to vertex 4 after second 2. Thus the probability for the frog is on the vertex 4 after 2 seconds is 1/3 * 1/2 = 1/6 = 0.16666666666666666.


Example 2:

Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 1, target = 7
Output: 0.3333333333333333
Explanation: The figure above shows the given graph. The frog starts at vertex 1, jumping with 1/3 = 0.3333333333333333 probability to the vertex 7 after second 1.


Example 3:

Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 20, target = 6
Output: 0.16666666666666666


Constraints:

• 1 <= n <= 100
• edges.length == n-1
• edges[i].length == 2
• 1 <= edges[i][0], edges[i][1] <= n
• 1 <= t <= 50
• 1 <= target <= n
• Answers within 10^-5 of the actual value will be accepted as correct.

struct Point {
int id, time;
double prob;
Point(int i, int t, double p) :id(i), time(t), prob(p) {};
};

class Solution {
public:
double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
vector<vector<int>> graph(n + 1, vector<int>(n + 1, 0));
for (int i = 0; i < edges.size(); ++i) {
graph[edges[i][0]][edges[i][1]] = 1;
graph[edges[i][1]][edges[i][0]] = 1;
}
vector<int> visited(n + 1, 0);
double prob = 1.0;
int time = 0;

queue<Point> q;
q.push(Point(1, 0, 1.0));
while (true) {
Point cur = q.front();
q.pop();
if (cur.id == target) {
prob = cur.prob;
time = cur.time;
break;
}
visited[cur.id] = 1;
int child = 0;
for (int i = 1; i <= n; ++i) {
if (visited[i] == 0 && graph[cur.id][i] == 1) {
++child;
}
}
for (int i = 1; i <= n; ++i) {
if (visited[i] == 0 && graph[cur.id][i] == 1) {
Point next(i, cur.time + 1, cur.prob / child);
q.push(next);
}
}
}

if (t < time)return 0;
else if (t == time)return prob;
else {
int child = 0;
for (int i = 1; i <= n; ++i) {
if (visited[i] == 0 && graph[target][i] == 1) {
++child;
}
}
if (child == 0)return prob;
else return 0;
}

}
};

# 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);
}
};

# LeetCode Maximum Binary Tree

Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

1. The root is the maximum number in the array.
2. The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
3. The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.

Construct the maximum tree by the given array and output the root node of this tree.

Example 1:

Input: [3,2,1,6,0,5]
Output: return the tree root node representing the following tree:

6
/   \
3     5
\    /
2  0
\
1


Note:

1. The size of the given array will be in the range [1,1000].

const int MINVAL = -999999999;

class Solution {
public:
TreeNode* makeTree(vector<int>& nums, int left, int right) {
if (left > right)return NULL;
if (left == right)return new TreeNode(nums[left]);
int maxid = -1, maxval = MINVAL;
for (int i = left; i <= right; ++i) {
if (nums[i] > maxval) {
maxval = nums[i];
maxid = i;
}
}
TreeNode* root = new TreeNode(nums[maxid]);
root->left = makeTree(nums, left, maxid - 1);
root->right = makeTree(nums, maxid + 1, right);
return root;
}
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return makeTree(nums, 0, nums.size() - 1);
}
};

# LeetCode Linked List in Binary Tree

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.

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};

//Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
void findStartNodes(vector<TreeNode*> &starts, TreeNode* root, int val) {
if (root->val == val)starts.push_back(root);
if (root->left != NULL)findStartNodes(starts, root->left, val);
if (root->right != NULL)findStartNodes(starts, root->right, val);
}

bool findSubPath(ListNode* head, TreeNode* root) {
return true;
}
else {
bool left_ans = false, right_ans = false;
if (root->left != NULL && root->left->val == head->next->val) {
}
if (root->right != NULL && root->right->val == head->next->val) {
}
return left_ans || right_ans;
}
}

bool isSubPath(ListNode* head, TreeNode* root) {
vector<TreeNode*> starts;

for (int i = 0; i < starts.size(); ++i) {
}

return false;
}
};

ListNode* genList(const vector<int> &vec) {
if (vec.size() == 0)return NULL;
for (int i = 1; i < vec.size(); ++i) {
ListNode* node = new ListNode(vec[i]);
cur->next = node;
cur = node;
}
}

// -1表示空节点
TreeNode* genTree(const vector<int> &vec) {
if (vec.size() == 0)return NULL;

vector<TreeNode*> nodes(vec.size(), NULL);
for (int i = 0; i < vec.size(); ++i) {
if (vec[i] != -1) {
nodes[i] = new TreeNode(vec[i]);
}
}

int npar = 0, nchild = 1;
while (true) {
if (nchild >= nodes.size())break;

int nnextpar = nchild;
while (npar < nnextpar) {
if (nodes[npar] != NULL) {
if (nchild >= nodes.size())break;
nodes[npar]->left = nodes[nchild++];
if (nchild >= nodes.size())break;
nodes[npar]->right = nodes[nchild++];
}
++npar;
}
npar = nnextpar;
}

return nodes[0];
}

int main() {
vector<int> vec = { 1,4,4,-1,2,2,-1,1,-1,6,8,-1,-1,-1,-1,1,3 };
TreeNode* root = genTree(vec);

vector<int> vec2 = { 1,4,2,6,8 };

Solution s;
return 0;
}

# hihoCoder 1542-无根数变有根树

hihoCoder 1542-无根数变有根树

### 输出

5 4
1 2
3 1
4 3
5 1

3 1 4 0 1