题目来源:https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/description/

标记难度:Medium

提交次数:3/3

代码效率:

  • 两遍递归:61.92%
  • 一遍递归:64.44%

题意

找出包含了树中所有深度最大的结点的最深的子树。

分析

一种简单的思路是,首先通过一遍深度优先搜索找出所有深度最大的结点的个数,然后再通过一遍深度优先搜索,计算左右子树中深度最大的结点的总个数,如果已经包含了所有最深的结点,则当前结点符合要求。因为是DFS,所以找到的第一个结点就是深度最大的子树的根。

但事实上我们可以通过递推的方法只进行一遍DFS。令f(root) = (depth, deepestTreeNode),其中depth表示在以root为根的子树中最深的结点的深度,deepestTreeNode表示在该子树中,包含了所有最深的结点的最深的子树。然后就可以递推了:

  • f(root.left).depth > f(root.right).depth时,说明最深的结点在左子树中,f(root) = (f(root.left).depth+1, f(root.left).deepestTreeNode)
  • f(root.left).depth < f(root.right).depth时,说明最深的结点在右子树中,f(root) = (f(root.right).depth+1, f(root.right).deepestTreeNode)
  • f(root.left).depth = f(root.right).depth时,说明两棵子树中都有最深的结点,f(root) = (f(root.left).depth+1, root)

最后返回的结果是f(root).deepestTreeNode[1]

值得注意的是,在上述解法中,是以root为根计算深度的,而非绝对深度;当然用相对整棵树的绝对深度去做也可以,具体代码差不多,就不再列出了。

代码

两遍递归

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
45
46
47
48
49
50
51
52
/**
* 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 {
private:
int maxDepth;
int maxNum;

void findMaxDepth(TreeNode* root, int depth) {
if (root == NULL)
return;
if (depth == maxDepth)
maxNum++;
else if (depth > maxDepth) {
maxDepth = depth;
maxNum = 1;
}
findMaxDepth(root->left, depth + 1);
findMaxDepth(root->right, depth + 1);
}

TreeNode* father;
int maxDepthNum(TreeNode* root, int depth) {
if (root == NULL)
return 0;
int sum = maxDepthNum(root->left, depth + 1) + maxDepthNum(root->right, depth + 1);
if (father != NULL)
return 0;
if (depth == maxDepth)
sum++;
if (sum == maxNum)
father = root;
return sum;
}

public:
TreeNode* subtreeWithAllDeepest(TreeNode* root) {
maxDepth = 0;
maxNum = 0;
findMaxDepth(root, 0);
// cout << maxDepth << ' ' << maxNum << endl;
father = NULL;
maxDepthNum(root, 0);
return father;
}
};

一遍递归

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
/**
* 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 {
// depth, deepestTree
typedef pair<int, TreeNode*> Node;
private:
Node dfs(TreeNode* root) {
if (root == NULL)
return {0, NULL};
Node leftNode(dfs(root->left));
Node rightNode(dfs(root->right));
if (leftNode.first < rightNode.first)
return {rightNode.first+1, rightNode.second};
if (leftNode.first > rightNode.first)
return {leftNode.first+1, leftNode.second};
return {leftNode.first+1, root};
}

public:
TreeNode* subtreeWithAllDeepest(TreeNode* root) {
Node node(dfs(root));
return node.second;
}
};

  1. One pass

题目来源:https://leetcode.com/problems/longest-univalue-path/description/

标记难度:Easy

提交次数:1/1

代码效率:39.40%

题意

给定一棵二叉树,找到树上满足下列条件的最长的路径:路径中每个结点的值都是相同的。

分析

这道题和Leetcode 124基本是一样的,只是递推条件换成了路径中的结点是否相等。不过我也是很不理解,怎么那道题是Hard,这道题就变成Easy了。

代码

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
/**
* 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 {
private:
int maxLength;

// number, length
pair<int, int> dfs(TreeNode* root) {
if (root == NULL)
return {-1, -1};
pair<int, int> leftPair = dfs(root->left);
pair<int, int> rightPair = dfs(root->right);

int length = 1;
if (leftPair.second != -1 && leftPair.first == root->val)
length = max(leftPair.second + 1, length);
if (rightPair.second != -1 && rightPair.first == root->val)
length = max(rightPair.second + 1, length);
int sum = length;
if (leftPair.second != -1 && leftPair.first == root->val && rightPair.second != -1 && rightPair.first == root->val)
length = max(leftPair.second + rightPair.second + 1, length);
maxLength = max(length, maxLength);

return {root->val, sum};
}

public:
int longestUnivaluePath(TreeNode* root) {
if (root == NULL)
return 0;

maxLength = -1;
dfs(root);
return maxLength - 1;
}
};

题目来源:https://leetcode.com/problems/binary-tree-maximum-path-sum/description/

标记难度:Hard

提交次数:2/3

代码效率:

  • 不太简洁的版本:98.55%
  • 比较简洁的版本:98.57%

题意

给定一棵非空二叉树,求树上所有路径中结点总和的最大值。

分析

这是一道比较简单的递推题。对于一棵有根树,显然树上的每一条路径都有一个深度最小的结点,所以这种做法可以覆盖到所有的路径。对于树上的每一个结点x,计算从x开始向下延伸的路径的最大结点总和,记为maxDown(x);显然,这一总和只有3种可能性,取的是其中的最大值:

  • x.val + maxDown(x.left)(如果左子树存在;此时路径向左子树延伸)
  • x.val + maxDown(x.right)(如果右子树存在;此时路径向右子树延伸)
  • x.val(因为负数结点值的存在,可能不如不延长路径;此时路径上只有x一个点)

通过DFS的方法可以比较方便地推出maxDown(x)。接下来的问题是,树上的路径除了向下延伸之外,还有另外一类,就是从某个结点开始,既向左也向右延伸。(之前忘了这种情况所以WA了一次。)因此需要另外计算maxSum(x) = max(maxDown(x), x.val + maxDown(x.left) + maxDown(x.right))。答案就是树上所有结点中maxSum的最大值。

代码

我的不太简洁的代码

这个代码对边界情况考虑得并不好,有更简洁也更好的写法。

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
/**
* 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 {
private:
int maxn;

int dfs(TreeNode* root) {
if (root == NULL)
return -1000000000;
int leftSum = dfs(root->left);
int rightSum = dfs(root->right);

int endSum = max(leftSum + root->val, rightSum + root->val);
endSum = max(endSum, root->val);
int sum = endSum;
endSum = max(endSum, leftSum + rightSum + root->val);
maxn = max(endSum, maxn);

return sum;
}

public:
int maxPathSum(TreeNode* root) {
if (root == NULL)
return 0;
maxn = root->val;
dfs(root);
return maxn;
}
};

比较简洁的代码

参考了Simple O(n) algorithm with one traversal through the tree的写法。

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
/**
* 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 {
private:
int maxn;

int dfs(TreeNode* root) {
if (root == NULL) return 0;
int leftSum = dfs(root->left);
int rightSum = dfs(root->right);

if (leftSum < 0) leftSum = 0;
if (rightSum < 0) rightSum = 0;
maxn = max(maxn, max(max(leftSum, rightSum) + root->val, leftSum + rightSum + root->val));

return max(leftSum, rightSum) + root->val;
}

public:
int maxPathSum(TreeNode* root) {
if (root == NULL)
return 0;
maxn = root->val;
dfs(root);
return maxn;
}
};

题目来源:https://leetcode.com/problems/maximum-frequency-stack/description/

标记难度:Medium

提交次数:1/1

代码效率:77.64%

题意

返回所有结点总数为N的完全二叉树。

分析

这是周赛(99)的第三题。比赛的时候我大概花了一个小时在这道题上,但是并没有做出来。我企图用一遍DFS完成所有的枚举任务,但事实上,如果不明确给定左子树和右子树的结点数目,是无法正常进行枚举的。直到最后我也没想出来怎么正常地枚举,于是我就挂了。


事实上这道题有非常明显的子问题结构,但我比赛的时候对这一点毫无知觉。显然,对于完全二叉树的每一个结点,要么它是一个叶结点,要么它的左右子树都是完全二叉树。而且显然完全二叉树的结点数目必然是奇数。于是我们可以通过递归解决这个问题:对于要求的结点总数N,枚举所有可能的左子树结点数(i,奇数)以及对应的右子树结点数(N - i - 1),然后把生成的子树拼在一起,得到所有可能的拼法。可以将N对应的所有树存起来,减少迭代的次数。

以及,令$N = 2k + 1$,则$N$个结点的不同构满二叉树的总数为卡特兰数$C_k = \frac{1}{k+1} \binom{2k}{k}$。从上述迭代公式应该是可以用数学归纳法证明的。[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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
* 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 {
private:
unordered_map<int, vector<TreeNode*>> cache;

void generate(int n) {
if (n <= 0 || n % 2 == 0)
return;
if (cache.find(n) != cache.end())
return;
if (n == 1) {
TreeNode* root = new TreeNode(0);
cache[1].push_back(root);
return;
}
for (int leftNum = 1; leftNum <= n - 1; leftNum += 2) {
generate(leftNum);
generate(n - 1 - leftNum);
for (TreeNode* ltree: cache[leftNum])
for (TreeNode* rtree: cache[n - 1 - leftNum]) {
TreeNode* root = new TreeNode(0);
root->left = copy(ltree);
root->right = copy(rtree);
cache[n].push_back(root);
}
}
}

TreeNode* copy(TreeNode* root) {
if (root == NULL)
return NULL;
TreeNode* newRoot = new TreeNode(0);
newRoot->left = copy(root->left);
newRoot->right = copy(root->right);
return newRoot;
}

public:
vector<TreeNode*> allPossibleFBT(int N) {
generate(N);
return cache[N];
}
};

  1. Leetcode 894 Solution

题目来源:https://leetcode.com/problems/mini-parser/description/

标记难度:Medium

提交次数:1/1

代码效率:99.61%

题意

把一个整数嵌套列表的字符串解析成一个整数嵌套列表对象。

分析

这道题显然没什么算法难度,重点是写法,以及一些需要注意的细节。

  • 要求是利用题目中给出的NestedInteger类型,而不是自己实现一个这种类型(我刚打开题目的时候被吓到了,以为要我自己用C++实现一个这种东西,那我肯定火速转Python啊。)
  • 既然是多层嵌套列表,那么用递归逐层进行处理是很自然的想法。换成栈节省开销也不错。
  • 如何在一层列表中判断每一项的界限?我最开始想直接用,作为分隔符split之,但很快发现这个想法大错特错,因为每一项自己内部也有嵌套的,。所以要加上判断[]的个数的条件。
  • 直接用stoistring转成int,也不用自己考虑-的问题了,标准库真好用……

代码

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* class NestedInteger {
* public:
* // Constructor initializes an empty nested list.
* NestedInteger();
*
* // Constructor initializes a single integer.
* NestedInteger(int value);
*
* // Return true if this NestedInteger holds a single integer, rather than a nested list.
* bool isInteger() const;
*
* // Return the single integer that this NestedInteger holds, if it holds a single integer
* // The result is undefined if this NestedInteger holds a nested list
* int getInteger() const;
*
* // Set this NestedInteger to hold a single integer.
* void setInteger(int value);
*
* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
* void add(const NestedInteger &ni);
*
* // Return the nested list that this NestedInteger holds, if it holds a nested list
* // The result is undefined if this NestedInteger holds a single integer
* const vector<NestedInteger> &getList() const;
* };
*/
class Solution {
private:
NestedInteger decomposeList(string s) {
// s是一个数字
// 好消息是,我感觉用了stoi之后,就不需要自己考虑-的问题了
if (s.length() > 0 && s[0] != '[')
return NestedInteger(stoi(s));
// s是一个列表
s = s.substr(1, s.length() - 2);
NestedInteger nestedInteger;
// 并不能简单地用,作为分隔,而是要找到一整个子列表
int start = 0, leftBrackets = 0;
for (int i = 0; i < s.length(); i++) {
if (s[i] == ',') {
if (leftBrackets != 0)
continue;
nestedInteger.add(decomposeList(s.substr(start, i - start)));
start = i + 1;
}
if (s[i] == '[')
leftBrackets++;
if (s[i] == ']')
leftBrackets--;
}
if (start < s.length())
nestedInteger.add(decomposeList(s.substr(start, s.length() - start)));
return nestedInteger;
}

public:
NestedInteger deserialize(string s) {
// 刚看到这个的时候我很懵逼
// 原来是让我们利用这个interface来做题啊……
return decomposeList(s);
}
};