题目来源:https://leetcode.com/problems/cousins-in-binary-tree/description/

标记难度:Easy

提交次数:1/1

代码效率:8ms

题意

定义二叉树中的“堂兄弟”结点:两个深度相同且父结点不同的结点。给定一棵结点值互异的二叉树和两个树中的结点值xy,问这两个结点是否为堂兄弟。

分析

只要遍历二叉树,并记录对应的两个结点的父节点和深度即可。不过为了降低复杂度,甚至可以干脆把每个结点的父节点和深度都记录下来,然后在里面查。

代码

这里遍历用的是DFS。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
private:
int father[102];
int depth[102];

void dfs(TreeNode* root, int d, int p) {
if (root == NULL) return;
father[root->val] = p;
depth[root->val] = d;
dfs(root->left, d + 1, root->val);
dfs(root->right, d + 1, root->val);
}

public:
bool isCousins(TreeNode* root, int x, int y) {
dfs(root, 0, -1);
return depth[x] == depth[y] && father[x] != father[y];
}
};

题目来源:https://leetcode.com/problems/smallest-string-starting-from-leaf/description/

标记难度:Medium

提交次数:2/4

代码效率:

  • BFS:4ms
  • 暴力:0ms

题意

给定一棵二叉树,令它的每个结点表示一个字符,问从每个叶结点开始,到树根结束的所有字符串中最小的字符串。

分析

考虑到这道题的数据范围(二叉树的最高层的叶结点数量大约最多是总结点数量的一半),完全可以把所有可能的字符串都生成出来,然后从里面找最小的……

另一种稍微不那么暴力的方法是做BFS,找到出现叶结点的第一层,然后再回溯(或者直接暴力……)。


这道题实现过程中还有另一个问题:如何把单个char赋值给一个string?事实上,直接赋值和cast是不行的;如果想要采用"" + 'a'这种写法,就更是大错特错了,这相当于将指向字符串""首位的指针加上(int) 'a'……

所以比较正确的方法是string(1, 'a')。不要把常量字符串加上char……[1]

代码

BFS

这份代码比较愚蠢的一点在于,它居然没有存每个结点对应的字符串,而是只存了每个结点的父节点的位置,这么写大概就是故意增加复杂度了……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
string smallestFromLeaf(TreeNode* root) {
vector<pair<TreeNode*, pair<int, int>>> q; // node, father, depth
int start = 0, end;
q.emplace_back(root, make_pair(-1, 0));
while (start < q.size()) {
end = q.size();
while (start < end) {
TreeNode* p = q[start].first;
int depth = q[start].second.second;
if (p->left != NULL) q.emplace_back(p->left, make_pair(start, depth + 1));
if (p->right != NULL) q.emplace_back(p->right, make_pair(start, depth + 1));
start++;
}
}

vector<pair<int, string>> ans; // index, string
for (int i = q.size() - 1; i >= 0; i--) {
TreeNode* p = q[i].first;
int depth = q[i].second.second;
if (p->left == NULL && p->right == NULL) ans.emplace_back(i, string(1, p->val + 'a'));
}

string minimal;
while (ans.size() > 0) {
vector<pair<int, string>> a;
minimal = "";
for (int i = 0; i < ans.size(); i++) {
minimal = minimal == "" || minimal > ans[i].second ? ans[i].second : minimal;
}
for (int i = 0; i < ans.size(); i++) {
if (ans[i].second == minimal) {
int last = q[ans[i].first].second.first;
if (last == -1) return minimal;
a.emplace_back(last, minimal + (char) (q[last].first->val + 'a'));
}
}
ans = a;
}

return minimal;
}
};

暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
private:
string ans;
void dfs(TreeNode* root, string s) {
if (root == NULL) return;
s += (char) (root->val + 'a');
if (root->left == NULL && root->right == NULL) {
reverse(s.begin(), s.end());
ans = ans == "" || s < ans ? s : ans;
return;
}
dfs(root->left, s);
dfs(root->right, s);
}

public:
string smallestFromLeaf(TreeNode* root) {
dfs(root, "");
return ans;
}
};

  1. stackoverflow - C++ convert from 1 char to string? [closed]

题目来源:https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/description/

标记难度:Medium

提交次数:1/1

代码效率:0ms

题意

给定一棵二叉树,定义每个结点的坐标如下:如果父结点的坐标是(X, Y),则左子结点的坐标是(X - 1, Y - 1),右子结点的坐标是(X - 1, Y + 1)。将横坐标相同的结点的值放在一个列表中,按值排序,并将这些列表按横坐标排序。

分析

总的来说是道简单的题,用一个map存放横坐标相同的结点的值,然后再排序即可。不过我倒是复习了一下怎么遍历C++ map……(如果不用语法糖的话)[1]

1
2
3
4
5
6
7
8
// 定义迭代器
map<int, vector<pair<int, int>>>::iterator it;
// 用迭代器进行遍历
for (it = nodeMap.begin(); it != nodeMap.end(); it++) {
// 用指针进行访问
sort(it->second.begin(),it->second.end());
...
}

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
private:
map<int, vector<pair<int, int>>> nodeMap; // x -> (-y, value)

void dfs(int x, int y, TreeNode* root) {
if (root == NULL) return;
nodeMap[x].emplace_back(-y, root->val);
dfs(x - 1, y - 1, root->left);
dfs(x + 1, y - 1, root->right);
}

public:
vector<vector<int>> verticalTraversal(TreeNode* root) {
dfs(0, 0, root);
vector<vector<int>> ans;
map<int, vector<pair<int, int>>>::iterator it;
for (it = nodeMap.begin(); it != nodeMap.end(); it++) {
vector<int> cols;
sort(it->second.begin(),it->second.end());
for (int i = 0; i < it->second.size(); i++)
cols.push_back(it->second[i].second);
ans.push_back(cols);
}
return ans;
}
};

  1. stackoverflow - Sort Vector in a Map c++

题目来源:https://leetcode.com/problems/distribute-coins-in-binary-tree/description/

标记难度:Medium

提交次数:1/1

代码效率:8ms

题意

有一颗二叉树,共有N个结点,每个结点上有若干枚硬币,硬币总数为N。每次操作可以把一枚硬币移动到相邻的结点。问最少进行几次操作,才能使每个结点上恰好有一枚硬币?

分析

我觉得这道题挺简单的……

我的思路很简单:先DFS,到达最底层之后判断每个叶结点上的硬币数量node->val是否恰好为1,如果大于1则把多出来的硬币向父结点移动,总移动数量+=node->val-1,如果小于1则把少的硬币向父结点移动,也就是移动-(1-node->val)枚硬币,总移动数量+=1-node->val。对于其他的结点,因为它们的子结点都已经递归处理完了,所以有多出来的硬币的时候,只能向上移动若干枚硬币或者负的若干枚硬币,也就是和叶结点差不多。

这里面比较好的是移动负数枚硬币这个想法,否则可能还得做第二次递归。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
private:
int ans;

int dfs(TreeNode* root) {
if (root == NULL) return 0;
int x = dfs(root->left) + dfs(root->right);
x += root->val;
ans += abs(x - 1);
root->val = 1;
return x - 1;
}

public:
int distributeCoins(TreeNode* root) {
ans = 0;
dfs(root);
return ans;
}
};

题目来源:https://leetcode.com/problems/flip-binary-tree-to-match-preorder-traversal/description/

标记难度:Medium

提交次数:1/1

代码效率:12ms

题意

给定一棵二叉树(每个结点对应的值都是唯一的)和一个前序遍历序列,问,能否通过交换其中一些结点左右子树,使得这棵树的前序遍历结果和给定的相同?

分析

既然是前序遍历,那么接下来的遍历序列中的第一个值必然需要和根结点相同,如果不等,则肯定不能实现。

接下来的问题就是要不要翻转。如果有左子结点,那么下一个值必然是左子结点的值;否则,如果有右子结点,下一个值必然是右子结点的值;否则(也就是说没有子结点),下一个值和之前的遍历相关,可能是父节点的右子结点之类的。

所以做出翻转的决策就很简单:如果左子结点有值,且这个值和遍历序列中预期的下一个值不等,那么就交换左右子树(显然不交换肯定不行了)。判断是否可行的方法也很简单,在上述翻转的基础上,每次都判断当前根结点的值和遍历序列中预期的值是否相等。


事实上,这个判断左子结点的方法是题解[1]里给出的。我比赛的时候用的是,判断是否有右子结点,如果有的话,它的值如果和预期的下一个值相等,才有可能有必要进行交换(当然也有可能根本实现不了)。这个判断本质上和上述方法是一样的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
vector<int> ans;
int index;
int n;

bool pre(TreeNode* root, vector<int>& voyage) {
if (root == NULL) return true;
if (root->val != voyage[index]) return false;
if (index == n - 1 && (root->left != NULL || root->right != NULL)) return false;
// cout << root->val << endl;
if (root->left != NULL && root->right != NULL && voyage[index + 1] == root->right->val) {
swap(root->left, root->right);
ans.push_back(root->val);
}
index++;
if (!pre(root->left, voyage)) return false;
if (!pre(root->right, voyage)) return false;
return true;
}

public:
vector<int> flipMatchVoyage(TreeNode* root, vector<int>& voyage) {
index = 0;
n = voyage.size();
bool ok = pre(root, voyage);
if (!ok) return {-1};
return ans;
}
};

  1. Leetcode Official Solution - 971. Flip Binary Tree To Match Preorder Traversal