Tag Archives:

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.

给定一棵多叉树(无向图),有n个顶点n-1条边。每个顶点上标了一个字母,问对于每个顶点,在它的子树中,与其字母相同的点有多少个。

每个节点维护一个26长的数组,记录该子树包含所有字母的频数。然后DFS,记录每个节点的这个数组,父节点的数组的值要累加上其直接孩子的这个数组的值。最后查表得到结果。代码如下:

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

本代码提交AC。

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

给定一个二叉树,要求树中某条路径的最大和。注意路径可以不经过叶子节点,也可以不经过根节点,即树中任意一条相连的路径即可。

使用递归的思路。对于一个节点,经过它的最大和路径有如下几种情况:

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

完整代码如下,辅助函数maxSum的返回值即为上面的前两种情况的最大值,maxSum返回之后有可能构成父节点的最大和。ans则是全局的最大和,还包括上面列的第三种情况。

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

本代码提交AC,用时36MS。

LeetCode Balance a Binary Search Tree

1382. 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.

给定一棵二叉搜索树,要求把这棵二叉搜索树进行平衡化处理。一棵平衡二叉搜索树首先要是一棵二叉搜索树,其次要是平衡的,平衡的意思是左右子树的高度差不超过1。

要构造一棵平衡二叉搜索树,其树的根节点应该是整个有序数组的中位数。所以先对原来的二叉搜索树先序遍历,得到有序数组,然后取数组中位数作为根节点,在左右子数组中递归构造二叉搜索树。

完整代码如下:

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

本代码提交AC,用时180MS。

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.

这题其实不是很hard。

给定一个无向树,节点编号是1~n。有一个青蛙开始在1号节点,每秒钟它会随机跳到与其相邻的未被访问的过的节点中,注意不能走回头路,访问过的节点不能再访问了。如果它周围的节点都被访问了,则它就在原地打转。问经过t秒,它跳到指定节点的概率是多少。

解法。从1号节点开始BFS,每到一个节点时,记录当前走过的时间以及走到当前节点的概率。计算概率也很简单,维护一个visited数组,看看有多少个未被访问的邻居child,则路径概率要乘上(1/child)。

还需要注意的是,如果走到目标节点的时间大于给定时间,则走不到目标节点;如果走的时间小于给定时间,则要看看目标节点还有没有未被访问的节点,如果没有的话,青蛙在目标节点原地打转,否则青蛙就跳走了不会再回来了。

完整代码如下:

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

	}
};

本代码提交AC,用时40MS。

LeetCode Time Needed to Inform All Employees

1376. 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.

一个公司有n个工人,每个工人有一个直属上级,公司最大的老板没有直属上级。当老板要下发通知时,他会通知他的直属下级,直属下级又一级一级往下通知。每个上级通知其所有下级的用时不同。问老板的通知要过多久能传达给所有工人。

这是一题多叉树的问题。本质上是求从根节点到所有叶子节点中的最长路径是多少。

想到树的问题一定要想到递归解法。对于任意一棵子树,【它到所有叶子节点的最长路径】等于【它到所有直属下级的长度】加上【所有直属下级到它们各自的所有叶子节点的最长路径的最大值】之和。

完整代码如下:

class Solution {
public:
	int maxTime(int headID, map<int, vector<int>>& employees, vector<int>& informTime) {
		if (employees.find(headID) == employees.end())return 0;

		int cur_time = informTime[headID];
		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);
		}
		return maxTime(headID, employees, informTime);
	}
};

本代码提交AC,用时1548MS。

LeetCode Print Binary Tree

655. 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].


很有意思的一个题,考察了二叉树的多个知识点。

给定一棵二叉树,要求逐层打印出每一层节点的值,而且子节点的位置要在父节点位置的下一层的左边。根据样例可以看到,打印出来的二维数组,如果把每层节点连起来的话,就是原来二叉树的形状。

观察样例可以发现这样一些规律:二叉树的高度就是二维数组的行数;假设高度为h,则二维数组的列数就是$2^h-1$。所以,首先根据LeetCode Maximum Depth of Binary Tree求出二叉树的高度,然后构造好目标大小的二维数组。

接着就是根据二叉树填充数组了。树的题目一般都是用递归来解决,这题也不例外。我们设计一个work函数,每次传入当前需要填充的树节点,二维数组的行号(层数),该节点所在的列数范围。当填充好这个节点后,递归的填充其左节点和右节点,层数加一,同时更新列数范围。

完整代码如下:

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

本代码提交AC,用时0MS,性能还是不错的。

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.


给定一个二叉搜索树,要求从树中搜索一个等于val的节点。二叉搜索树是左子树节点小于根节点,右子树节点大于根节点的树。所以搜索时只需要和根节点比较大小,递归的在左子树或右子树中搜索即可。

完整代码如下:

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

本代码提交AC,用时52MS

LeetCode Maximum Binary Tree

654. 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].

给定一个数组,要求用数组元素创建一个最大树。最大树的含义是,根节点是数组中的最大元素,左子树是以数组中最大元素划分的左子数组递归构造最大树,右子树以右子数组递归构造最大树。

简单题,设计一个子数组makeTree(nums,left,right),每次从区间[left,right]中找到最大元素,然后构造根节点,最后递归在左子数组和右子数组中构造最大树。

完整代码如下:

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

本代码提交AC,用时100MS。

我原本以为可以先求出前k项的最大值和后k项的最大值,后续构造最大树的时候只需要查找这两个最大值就可以,事实上这是不行的,因为用最大值划分之后,求最大值和最小值的区间就不是前k项或者后k项了,有可能是某个中间的子区间,所以行不通,只能用上述暴力方法了。

LeetCode Linked List in Binary Tree

1367. 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.

给定一棵二叉树和一个链表,问链表中的元素是否是二叉树中某一条向下的路径的一部分,结合题中的例子,很容易理解题意。

我的做法是,对于链表head和二叉树root,首先在root中找到所有值是head的节点,也就是找到树中的开始比对的节点。然后,链表中的节点和树中的节点递归比对,直到走完链表比对成功,或者出现不相等或树没有孩子节点,比对失败。

完整代码如下:

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

 //Definition for singly-linked list.
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) {
		if (head->next == NULL) {
			return true;
		}
		else {
			bool left_ans = false, right_ans = false;
			if (root->left != NULL && root->left->val == head->next->val) {
				left_ans =  findSubPath(head->next, root->left);
			}
			if (root->right != NULL && root->right->val == head->next->val) {
				right_ans = findSubPath(head->next, root->right);
			}
			return left_ans || right_ans;
		}
	}

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

		for (int i = 0; i < starts.size(); ++i) {
			if (findSubPath(head, starts[i]))return true;
		}

		return false;
	}
};

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

// -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 };
	ListNode* head = genList(vec2);

	Solution s;
	bool ans = s.isSubPath(head, root);
	return 0;
}

本代码提交AC,用时36MS。

之前在LeetCode Minimum Depth of Binary Tree中我曾写过一个genTree的辅助函数,根据数组生成对应的二叉树。但是那个函数要求二叉树是完全二叉树,如果二叉树残缺很多节点的话,构造数组很麻烦。比如用之前的函数构造此题示例的二叉树,则数组中需要添加很多-1,很麻烦而且容易出错。

借此题的机会,我重写了一个genTree的辅助函数,如上代码所示。这个构造函数方便很多,对于输入数组,每个节点的左右孩子依次追加在数组的后面,也不用为空节点的孩子保留-1。genTree的时候先构造好所有节点,然后根据规则把这些节点连接起来。具体使用方法可以看代码中的示例。

hihoCoder 1542-无根数变有根树

hihoCoder 1542-无根数变有根树

#1542 : 无根数变有根树

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

给定一棵包含 N 个节点的无根树,小Hi想知道如果指定其中某个节点 K 为根,那么每个节点的父节点是谁?

输入

第一行包含一个整数 N 和 K。1 ≤ N ≤ 1000, 1 ≤ K ≤ N。 以下N-1行每行包含两个整数 a 和 b,代表ab之间存在一条边。 1 ≤ ab ≤ N。 输入保证是一棵树。

输出

输出一行包含 N 个整数,分别代表1~N的父节点的编号。对于 K 的父节点输出0。
样例输入
5 4
1 2
3 1
4 3
5 1
样例输出
3 1 4 0 1

给定一个无根树(其实就是DAG),如果以该树的某个顶点K为根,要求输出每个节点的父节点。 简单题,以K为根,进行DFS,遍历过程中记录每个节点的父节点就好了。完整代码如下: [cpp] #include<iostream> #include<vector> #include<algorithm> #include<unordered_set> #include<string> #include<unordered_map> #include<queue> using namespace std; const int kMaxN = 1005; int n, k; vector<int> parent(kMaxN, 0); vector<vector<int>> graph(kMaxN, vector<int>(kMaxN, 0)); void DFS(int node, int pre) { parent[node] = pre; graph[node][pre] = 0; graph[pre][node] = 0; for (int i = 1; i <= n; ++i) { if (graph[node][i] == 1) { DFS(i, node); } } graph[node][pre] = 1; graph[pre][node] = 1; } int main() { //freopen("input.txt", "r", stdin); scanf("%d %d", &n, &k); int a, b; for (int i = 0; i < n – 1; ++i) { scanf("%d %d", &a, &b); graph[a][b] = 1; graph[b][a] = 1; } DFS(k, 0); for (int i = 1; i <= n; ++i) printf("%d ", parent[i]); return 0; } [/cpp] 本代码提交AC,用时42MS。]]>