arttnba3's old blog

- arttnba3的垃圾堆积处 -

0%

【OJ-0x0005-Leetcode】树部分write up by arttnba3

Posted on Edited on In

0x00.绪论

本来不想这么快又开一篇新的blog的（毕竟一篇OJ就是一个坑，前面的好多坑才刚刚开挖），不过因为刚好做了每日一题的前置题目而刚好这道题又是树/图题所以想找个地方记录下来因此就开了一篇新博客

题好难做啊.jpg

pre.什么是树

树是一种抽象数据类型（ADT）或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由 n(n>0)n(n>0) 个有限节点组成一个具有层次关系的集合。

image.png

把它叫做「树」是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

它具有以下的特点：

每个节点都只有有限个子节点或无子节点；
没有父节点的节点称为根节点；
每一个非根节点有且只有一个父节点；
除了根节点外，每个子节点可以分为多个不相交的子树；
树里面没有环路。

链接：https://leetcode-cn.com/tag/tree/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

构造一棵树的最简单的代码如下:

1
2
3
4
5
6
typedef struct tree
{
    int val;
    struct tree * next;
    struct tree * child;
}

这种结构是以下图的方式来保存一棵树的：

image.png

构造一棵二叉树的代码如下：

1
2
3
4
5
6
typedef struct tree
{
    int val;
    struct tree * left;
    struct tree * right;
}

是不是很相似呢？其实可以把树的图歪过来康康…

0x01.难度：简单

0x00.二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

3

/ \
9 20
/ \
15 7
返回它的最大深度 3 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我们很容易想到使用递归的方式获取其最大深度，即深度优先搜索

故构造代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


int maxDepth(struct TreeNode* root){
    if(root==NULL)
        return 0;
    if(root->left==NULL&&root->right==NULL)
        return 1;
    int i=0,j=0;
    i=maxDepth(root->left)+1;
    j=maxDepth(root->right)+1;
    return i>j?i:j;
}

当然，递归会占用大量栈空间，因此内存消耗上并不是那么的理想（

image.png

0x01.翻转二叉树

翻转一棵二叉树。

示例：

输入：

 4

/ \
2 7
/ \ / \
1 3 6 9
输出：

 4

/
7 2
/ \ /
9 6 3 1
备注:
这个问题是受到 Max Howell 的 原问题 启发的 ：

谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/invert-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

注：该题为2020.9.16的每日一题

很常规的也很简单的一道题目，只需逐层交换左右节点即可（homebrew的开发者居然写不出这个题么（估计是太紧张le（👈不要在意这家伙天天乱讲

解法一：递归

一层一层交换结点的做法，我们很容易就想到递归，故构造代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


struct TreeNode* invertTree(struct TreeNode* root)
{
    if(root == NULL)
        return root;
    struct TreeNode * temp;
    temp = root->left;
    root->left = root->right;
    root->right = temp;
    invertTree(root->left);
    invertTree(root->right);
    return root;
}

当然，递归调用会占用大量的栈空间（每次进行函数调用都会生成一个新的栈帧），所以空间复杂度上不是很好看（

image.png

解法二：广度优先搜索（队列）

大概过程如下：

  • 头结点入队
  • 交换左右结点
  • 左右结点入队
  • 头结点出队

队列为空时停止即可

因为数据范围不像OI那么变态（x），所以直接用一个很小的数组来储存即可

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


struct TreeNode* invertTree(struct TreeNode* root)
{
    if(root == NULL)
        return root;
    int start=0, end=1;
    struct TreeNode * (queue[1000]), *temp;
    queue[start] = root;
    while(start!=end)
    {
        if(queue[start] != NULL)
        {
            temp = queue[start]->left;
            queue[start]->left = queue[start]->right;
            queue[start]->right = temp;
            queue[end] = queue[start]->left;
            queue[end+1] = queue[start]->right;
            end += 2;
        }
        start++;
    }
    return root;
}

image.png

以及这个故事实在是太搞了

image.png

0x02. 左叶子之和

计算给定二叉树的所有左叶子之和。

示例：

3
/ \
9 20
/ \
15 7

在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sum-of-left-leaves
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：深度优先搜索（DFS）

一层一层地搜下去，若左结点为叶子结点（无子女）则加上左结点的值，否则搜索子结点，若右结点不为子结点则搜索右结点的子节点

得代码如下：

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

bool isLeaf(struct TreeNode * root)
{
    return !root->left && !root->right;
}

int dfs(struct TreeNode* root)
{
    int ans = 0;
    ans += root->left ? (isLeaf(root->left) ? root->left->val : dfs(root->left)) : 0;
    ans += (root->right!=NULL&&!isLeaf(root->right)) ? dfs(root->right) : 0;
    return ans;
}

int sumOfLeftLeaves(struct TreeNode* root)
{
    return root ? dfs(root) : 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//利用三目运算符的一行流
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int sumOfLeftLeaves(struct TreeNode* root)
{
    return root ? (root->left && !root->left->left && !root->left->right ? root->left->val + sumOfLeftLeaves(root->right) : sumOfLeftLeaves(root->left)+sumOfLeftLeaves(root->right)) : 0;
}

image.png

解法二：广度优先搜索（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
45
46
47
48
49
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

bool isLeafNode(struct TreeNode *node) 
{
    return !node->left && !node->right;
}

int sumOfLeftLeaves(struct TreeNode *root) 
{
    if (!root) 
    {
        return 0;
    }
    struct TreeNode **q = malloc(sizeof(struct TreeNode *) * 1001);
    int left = 0, right = 0;
    q[right++] = root;
    int ans = 0;
    while (left < right) 
    {
        struct TreeNode *node = q[left++];
        if (node->left) 
        {
            if (isLeafNode(node->left)) 
            {
                ans += node->left->val;
            } 
            else 
            {
                q[right++] = node->left;
            }
        }
        if (node->right) 
        {
            if (!isLeafNode(node->right)) 
            {
                q[right++] = node->right;
            }
        }
    }
    return ans;
}

当然，这么做有一个缺点就是需要提前开辟较大的空间

image.png

0x03.把二叉搜索树转换为累加树

给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

例如：

输入: 原始二叉搜索树:
5
/
2 13

输出: 转换为累加树:
18
/
20 13

注意：本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/convert-bst-to-greater-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

注：该题为2020.9.21的每日一题

二叉搜索树有一个特点就是结点左子树的结点都比该结点小，右子树的结点都比该结点大，因而叫二叉搜索树，可以用以大幅缩短搜索的时间

解法：深度优先搜索 + 反序中序遍历

由于二叉查找树的这个特性，我们考虑递归实现的深度优先搜索算法，通过反序中序遍历来实现，过程如下：

  • 遍历右子树，将右子树结点值加到summary
  • 将当前结点值加到summary
  • 将当前结点值置为summary
  • 遍历左子树

每个结点需要一个额外的栈空间，因而空间复杂度为O(N)；需要遍历每个结点一次，因而时间复杂度为O(N)

构造代码如下：

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


void dfs(struct TreeNode* root, int *sum)
{
    if(!root)
        return;
    dfs(root->right,sum);
    *sum+=root->val;
    root->val=*sum;
    dfs(root->left,sum);
    return;
}

struct TreeNode* convertBST(struct TreeNode* root)
{
    int sum = 0;
    dfs(root, &sum);
    return root;
}

image.png

0x04. 合并二叉树

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:

输入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/ \
4 5
/ \ \
5 4 7
注意: 合并必须从两个树的根节点开始。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-binary-trees
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

注：本题为2020.9.23的每日一题

解法：递归 + 深度优先搜索（DFS）

逐层递归，合并到t1上：

  • t1、t2若为空则直接返回其中非空的那一个
  • 将t2的val加到t1的val上
  • 合并t1左与t2左
  • 合并t1右与t2右

得到代码如下：

时间复杂度：

搜索的次数和结点数量线性增长，故时间复杂度为O(N)

空间复杂度：

需要的栈空间数量和结点数量线性增长，故空间复杂度为O(N)

C语言版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2)
{
    if(!t1)
        return t2;
    if(!t2)
        return t1;
    t1->val += t2->val;
    t1->left = mergeTrees(t1->left,t2->left);
    t1->right = mergeTrees(t1->right,t2->right);
    return t1;
}

wXgivj.png

Python语言版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        if t1 == None:
            return t2
        if t2 == None:
            return t1
        t1.val += t2.val
        t1.left = self.mergeTrees(t1.left, t2.left)
        t1.right = self.mergeTrees(t1.right, t2.right)
        return t1

wXgJVx.png

0x05.二叉搜索树中的众数

给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

假定 BST 有如下定义：

结点左子树中所含结点的值小于等于当前结点的值
结点右子树中所含结点的值大于等于当前结点的值
左子树和右子树都是二叉搜索树
例如：
给定 BST [1,null,2,2],

1
\
2
/
2
返回[2].

提示：如果众数超过1个，不需考虑输出顺序

进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-mode-in-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法：递归 + 深度优先搜索（DFS）

考虑到二叉搜索树中左子树所有结点的值小于当前结点值小于右子树所有结点的值，故还是采取深度优先搜索算法

递归中序遍历，由于二叉搜索树的特殊性质，我们遍历的顺序一定是排序好的

故构造代码如下：

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

int max;//数量最多的数的数量
int num;//前一结点的连续结点个数
int pre;//前一结点的值
int size;//返回的数组的大小
int *retn;//返回的数组

int* findMode(struct TreeNode* root, int* returnSize)
{
    retn = (int*)malloc(sizeof(int)*2150);//这是多次尝试后得出来的一个大概的边界值233333
    if(!root)
    {
        *returnSize = 0;
        return retn;
    }
    max = 0;
    pre = 0xdeadbeef;
    size = 0;
    num = 0;
    dfs(root);
    *returnSize = size;
    return retn;
}

void dfs(struct TreeNode * root)
{
    if(!root)
        return;
    dfs(root->left);

    if(root->val == pre)
        num++;
    else//新序列
        num = 1;
    
    if(num > max)//相同结点数量比max还多，则进行重置
    {
        size = 0;
        retn[size++] = root->val;
        max = num;
    }
    else if(num == max)//否则，放入数组中
    {
        retn[size++] = root->val;        
    }

    pre = root->val;//储存该结点值，继续遍历下一结点

    dfs(root->right);
    
}

wxTxSA.png

0x06.二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

注：该题为2020.9.27的每日一题

解法：深度优先搜索（DFS）

二叉搜索树（BST）有一个很重要的性质就是左子树所有结点都小于当前节点，右子树所有结点都大于当前结点，所以我们可以直接通过比较结点的值来进行判断

构造代码如下：

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) 
{
    if(p == q)
        return p;
    
    bool flag1 = p->val > root->val;
    bool flag2 = q->val > root->val;
    if(flag1 != flag2)
        return root;
    
    if(p == root || q == root)
        return root;

    if(flag1)
        return lowestCommonAncestor(root->right,p,q);

    return lowestCommonAncestor(root->left,p,q);
}

@_I_39NAGH0__CROGOJD4XX.png

0x07 - 二叉搜索树的最小绝对差

给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。

示例：

输入：

1

3
/
2

输出：
1

解释：
最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。

提示：

树中至少有 2 个节点。
本题与 783 https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/ 相同

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法：深度优先搜索 + 中序遍历

因为是二叉搜索树，所以当进行中序遍历时肯定会按照从小到大的结点进行遍历

最小绝对差肯定出现在相邻值结点中，这里就不再过多赘叙了

构造代码如下：

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int ans = 0xffff;
int pre = -1;

void dfs(struct TreeNode* root)
{
    if(!root)
        return ;
    dfs(root->left);
    if(pre == -1)
        pre = root->val;
    else
    {
        ans = (root->val - pre) < ans ? (root->val - pre) : ans;
        pre = root->val;
    }
    dfs(root->right);
}

int getMinimumDifference(struct TreeNode* root)
{
    pre = -1;
    ans = 0xffff;
    dfs(root);
    return ans;
}

image.png

0x08 - 二叉搜索树节点最小距离

给定一个二叉搜索树的根节点 root，返回树中任意两节点的差的最小值。

示例：

输入: root = [4,2,6,1,3,null,null]
输出: 1
解释:
注意，root是树节点对象(TreeNode object)，而不是数组。

给定的树 [4,2,6,1,3,null,null] 可表示为下图:

      4
    /   \
  2      6
 / \    
1   3

最小的差值是 1, 它是节点1和节点2的差值, 也是节点3和节点2的差值。

注意：

二叉树的大小范围在 2 到 100。
二叉树总是有效的，每个节点的值都是整数，且不重复。
本题与 530：https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/ 相同

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

和上一题一样

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int pre;
int min;

void dfs(struct TreeNode * root)
{
    if(!root)
        return;
    dfs(root->left);
    if(pre != -1)
        min = (root->val - pre > min) ? min : (root->val - pre);
    pre = root->val;
    dfs(root->right);
}

int minDiffInBST(struct TreeNode* root)
{
    pre = -1;
    min = 0xffff;
    dfs(root);
    return min;
}

image.png

0x02.难度：中等

0x00.二叉树中的列表

给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。

如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，那么请你返回 True ，否则返回 False 。

一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。

示例 1：

输入：head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出：true
解释：树中蓝色的节点构成了与链表对应的子路径。

示例 2：

输入：head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出：true

示例 3：

输入：head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出：false
解释：二叉树中不存在一一对应链表的路径。

提示：

二叉树和链表中的每个节点的值都满足 1 <= node.val <= 100 。
链表包含的节点数目在 1 到 100 之间。
二叉树包含的节点数目在 1 到 2500 之间。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-in-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这题咋一看很难的样子，其实仔细一想，这不就是我们常用的递归算法中的二叉树的前序遍历🐎，一股熟悉的感觉扑面而来www

前序遍历：先遍历根节点，再遍历左节点，再遍历又节点

不熟悉递归算法的可以先看看我以前的博文，然后把OpenJudge.1700:八皇后问题给做了，那么这道题的算法你基本上也就该明白了

思路：递归前序遍历二叉树查找对应的"链表"，找到了直接返回True，遍历完整棵树都没找到则返回False

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool seek(struct ListNode* head, struct TreeNode* root)//此函数进行对比
{
    if(head == NULL)//链表遍历完了，直接true
        return true;
    if(root == NULL)//链表没完树先到头肯定是false
        return false;
    if(head->val!=root->val)//遍历到一半不一样，肯定是false
        return false;
    return seek(head->next,root->left)||seek(head->next,root->right);
}


bool isSubPath(struct ListNode* head, struct TreeNode* root)//此函数仅用作开始对比的入口
{
    if(root == NULL)
        return false;
    return seek(head,root)||isSubPath(head,root->left)||isSubPath(head,root->right);//根节点||左孩子做根节点||右孩子做根节点
}

QQ截图20200423032409.png

0x01. 冗余连接

在本问题中, 树指的是一个连通且无环的无向图。

输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点u 和v的无向图的边。

返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。

示例 1：

输入: [[1,2], [1,3], [2,3]]
输出: [2,3]
解释: 给定的无向图为:
1
/ \
2 - 3
示例 2：

输入: [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]
解释: 给定的无向图为:
5 - 1 - 2
| |
4 - 3
注意:

输入的二维数组大小在 3 到 1000。
二维数组中的整数在1到N之间，其中N是输入数组的大小。
更新(2017-09-26):
我们已经重新检查了问题描述及测试用例，明确图是无向 图。对于有向图详见冗余连接II。对于造成任何不便，我们深感歉意。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/redundant-connection
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

图有的时候是树，树无时无刻是图

解法：并查集

由于本题所给的是无向图，故不需要考虑边的方向

考虑并查集算法：将所有联通的点都纳入数个集合中以方便查找：

  • 初始化每个点为一个自身的集合
  • 逐条边读入，分别查找两端点所属集合
  • 两点所属集合不同则合并两集合，否则返回该条边即可

初版代码

一开始我是这么写的：

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
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int set[10000][10000]={0};//第一维分配给每一个点，第二维作为该点的集合保存其他附庸点
int set_size[10000][2]={0};//0表示所属集合，1表示集合中点的数量

int find_x(int src)
{
    return set_size[src][0] == src ? src : find_x(set_size[src][0]);
}

void union_set(int s1, int s2)
{    
    while(set_size[s1][0]!=s1)
        s1 = set_size[s1][0];
    while(set_size[s2][0]!=s2)
        s2 = set_size[s2][0];
    for(int i=0;i<=set_size[s2][1];i++)
    {
        set_size[s1][1]++;
        set[s1][set_size[s1][1]] = set[s2][i];
    }
    set_size[s2][0] = s1;
}

int* findRedundantConnection(int** edges, int edgesSize, int* edgesColSize, int* returnSize)
{    
    *returnSize = 2;
    int *ret = malloc(sizeof(long long int) * 2);
    ret[0] = 0;
    ret[1] = 0;
    
    for(int i=1;i<=edgesSize;i++)
    {
        set_size[i][0] = set[i][0] = i;
        set_size[i][1] = 1;
    }

    int start, end;
    int flag1,flag2;
    for(int i=0;i<edgesSize;i++)
    {
        start = edges[i][0];
        end = edges[i][1];
        flag1 = find_x(start);
        flag2 = find_x(end);
        if(flag1 == flag2)
        {
            ret[0] = start;
            ret[1] = end;
            return ret;
        }
        union_set(start,end);
    }
    return ret;
}

由于一开始我们就初始化一个较大的二维数组，故空间复杂度上比较吃亏

image.png

优化：减少冗余步骤与空间

我们尝试改变之前一拍脑门时繁复冗杂的写法，在归并时仅记录长度进行归并即可（即小集合归并到大集合），并使用动态数组以尽量减少空间使用

思路还是合之前的一样，构造代码如下：

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
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int *set;
int *set_size;

int find_x(int src)
{
    return set[src] == src ? src : find_x(set[src]);
}

void union_set(int s1, int s2)
{    
    s1 = find_x(s1);
    s2 = find_x(s2);
    if(set_size[s1]<set_size[s2])
    {
        set_size[s2] += set_size[s1];
        set[s1] = set[s2];
    }
    else
    {
        set_size[s1] += set_size[s2];
        set[s2] = set[s1];
    }
}

int* findRedundantConnection(int** edges, int edgesSize, int* edgesColSize, int* returnSize)
{    
    *returnSize = 2;
    int *ret = malloc(sizeof(int) * 2);
    set = (int*)malloc(sizeof(int)*(edgesSize+5));
    set_size = (int*)malloc(sizeof(int)*(edgesSize+5));
    ret[0] = 0;
    ret[1] = 0;
    
    for(int i=1;i<=edgesSize;i++)
    {
        set[i] = i;
        set_size[i] = 1;
    }

    int start, end;
    int flag1,flag2;
    for(int i=0;i<edgesSize;i++)
    {
        start = edges[i][0];
        end = edges[i][1];
        flag1 = find_x(start);
        flag2 = find_x(end);
        if(flag1 == flag2)
        {
            ret[0] = start;
            ret[1] = end;
            return ret;
        }
        union_set(start,end);
    }
    return ret;
}

（减少差不多一半空间，但是看起来并没有什么用…）

image.png

0x02.从二叉搜索树到更大和树

给出二叉 搜索 树的根节点，该二叉树的节点值各不相同，修改二叉树，使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树。

示例：

image.png

输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

提示：

树中的节点数介于 1 和 100 之间。
每个节点的值介于 0 和 100 之间。
给定的树为二叉搜索树。

注意：该题目与 538: https://leetcode-cn.com/problems/convert-bst-to-greater-tree/ 相同

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题和上面【难度：简单】0x03.把二叉搜索树转换为累加树是一模一样的（所以说为什么换一个名字难度就变成中等了啊

二叉搜索树有一个特点就是结点左子树的结点都比该结点小，右子树的结点都比该结点大，因而叫二叉搜索树，可以用以大幅缩短搜索的时间

解法：深度优先搜索 + 反序中序遍历

由于二叉查找树的这个特性，我们考虑递归实现的深度优先搜索算法，通过反序中序遍历来实现，过程如下：

  • 遍历右子树，将右子树结点值加到summary
  • 将当前结点值加到summary
  • 将当前结点值置为summary
  • 遍历左子树

每个结点需要一个额外的栈空间，因而空间复杂度为O(N)；需要遍历每个结点一次，因而时间复杂度为O(N)

构造代码如下：

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int sum;

void dfs(struct TreeNode* root)
{
    if(!root)
        return;
    dfs(root->right);
    sum+=root->val;
    root->val=sum;
    dfs(root->left);
    return;
}


struct TreeNode* bstToGst(struct TreeNode* root)
{
    sum = 0;
    dfs(root);
    return root;
}

image.png

0x03.路径总和 II

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22，

       5
      / \
     4   8
    /   / \
   11  13  4

/ \ /
7 2 5 1

返回:

[
[5,4,11,2],
[5,8,4,5]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法：深度优先搜索（DFS）+ 递归中序遍历

中序遍历，一层一层地搜下去就完事了，用一个栈来保存路径，遇到叶子结点且刚好到了这一层时sum已经被减到0了就保存路径

需要注意的是在每一层搜索结束后都要将该层结点弹出栈

构造代码如下：

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int **retn;
int *set;
int nums;
int retn_nums;

void dfs(struct TreeNode* root, int sum, int** returnColumnSizes)
{
    if(!root)
        return;
    
    sum -= root->val;
    set[nums++] = root->val;

    if(!root->left && !root->right && !sum)
    {
        int * path = (int*) malloc(sizeof(int) * nums);
        memcpy(path, set, sizeof(int) * nums);
        (*returnColumnSizes)[retn_nums] = nums;
        retn[retn_nums++] = path;
    }

    dfs(root->left,sum,returnColumnSizes);
    dfs(root->right,sum,returnColumnSizes);
    nums--;
}

int** pathSum(struct TreeNode* root, int sum, int* returnSize, int** returnColumnSizes)
{
    retn_nums = nums = 0;
    set = (int*) malloc(sizeof(int)*1000);
    retn = (int**)calloc(1000,sizeof(int*));
    if(!root)
    {
        *returnSize = 0;
        (*returnColumnSizes)[0] = 0;
        return NULL;
    }
    dfs(root,sum,returnColumnSizes);
    *returnSize = retn_nums;
    return retn;
}

image.png

0x04.填充每个节点的下一个右侧节点指针 II

给定一个二叉树

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

进阶：

你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

示例：

image.png

输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。

提示：

树中的节点数小于 6000
-100 <= node.val <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

注：本题为2020.9.28的每日一题

解法一：层次遍历

我们考虑到当我们填充next指针将每一层的结点都连接起来后，该层所有结点便构成了一个单向链表，我们可以通过遍历每一层的链表来构造下一层的链表

大致过程如下图

BD12E33FCF6E3B97FC6DB3AF5B645CF2.png

时间复杂度：

由于每个结点都要遍历一次，故时间复杂度为O(N)

空间复杂度：

由于没有使用到额外的空间，故空间复杂度为O(1)

C语言版：

我么可以得到如下代码：

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
/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *left;
 *     struct Node *right;
 *     struct Node *next;
 * };
 */

struct Node * last_node, *next_start;

void connectList(struct Node * node)
{
    if(last_node)
    {
        last_node->next = node;
    }
    if(!next_start)
    {
        next_start = node;
    }
    last_node = node;
}

struct Node *connect(struct Node *root) 
{
    if (!root)
        return NULL;

    struct Node *start = root;
    while(start)
    {
        last_node = NULL, next_start = NULL;
        while(start)
        {
            if(start->left)
                connectList(start->left);
            if(start->right)
                connectList(start->right);
            start = start->next;
        }
        start = next_start;
    }
    return root;
}

_XU940OX_R1_5XJK_H@N~5I.png

Python语言版：

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
"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def __init__(self):
        self.last_node: 'Node'
        self.next_start: 'Node'


    def connect(self, root: 'Node') -> 'Node':
        if root == None:
            return root

        start = root

        while start != None:
            self.last_node = None
            self.next_start = None

            while start != None:
                if start.left != None:
                    if self.last_node != None:
                        self.last_node.next = start.left

                    if self.next_start == None:
                        self.next_start = start.left

                    self.last_node = start.left

                if start.right != None:
                    if self.last_node != None:
                        self.last_node.next = start.right

                    if self.next_start == None:
                        self.next_start = start.right

                    self.last_node = start.right

                start = start.next

            start = self.next_start
        
        return root
                


    def connectList(self, node: 'Node'):

        if self.last_node != None:
            self.last_node.next = node

        if self.next_start == None:
            self.next_start = node

        self.last_node = node

![XTJUK27UN3_66_OSL5`_BZB.png](https://i.loli.net/2020/09/28/ywXFL85CP4Zm2B6.png)

0x05.二叉树的后序遍历

给定一个二叉树，返回它的 后序 遍历。

示例:

输入: [1,null,2,3]
1

2
/
3

输出: [3,2,1]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

注：本题为2020.9.29的每日一题

解法一：深度优先搜索（DFS） + 递归后续遍历

后序遍历的顺序是左→右→根，使用递归可以三分钟内解决

时间复杂度：

每个结点都过一遍，所以时间复杂度是O(N)

空间复杂度：

每个结点都要开辟一个单独的栈帧空间，故空间复杂度为O(N)

构造代码如下：

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int * retn;
int size;
void dfs(struct TreeNode* root)
{
    if(!root)
        return;

    if(root->left)
        dfs(root->left);
    
    if(root->right)
        dfs(root->right);

    retn[size++] = root->val;
}

int* postorderTraversal(struct TreeNode* root, int* returnSize)
{
    
    if(!root)
    {
        *returnSize = 0;
        return NULL;
    }
    retn = (int*) malloc(sizeof(int)*1000);
    size = 0;

    dfs(root);
    *returnSize = size;

    return retn;
}

_B35__WY2L_Z`E_`27DA_FM.png

0x06. 二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。

例如,

给定二叉搜索树:

    4
   / \
  2   7
 / \
1   3

和 插入的值: 5
你可以返回这个二叉搜索树:

     4
   /   \
  2     7
 / \   /
1   3 5

或者这个树也是有效的:

     5
   /   \
  2     7
 / \   
1   3
     \
      4

提示：

给定的树上的节点数介于 0 和 10^4 之间
每个节点都有一个唯一整数值，取值范围从 0 到 10^8
-10^8 <= val <= 10^8
新值和原始二叉搜索树中的任意节点值都不同

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/insert-into-a-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

注：本题为2020.9.30的每日一题

解法：深度优先搜索（DFS）

深度优先搜索遍历这棵树， 插入值大于结点值则往右子树插，否则往左子树插

递归可以很方便地解决这个问题

时间复杂度：

每个结点都有可能过一遍，所以时间复杂度是O(N)

空间复杂度：

每个结点都要开辟一个单独的栈帧空间，故空间复杂度为O(N)

构造代码如下：

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
void dfs(struct TreeNode* root, int val)
{
    if(!root)
        return;

    if(val > root->val)
    {
        if(!root->right)
        {
            root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
            root->right->val = val;
            root->right->left = NULL;
            root->right->right = NULL;
        }
        else
        {
            dfs(root->right, val);
        }
    }
    else
    {
        if(!root->left)
        {
            root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
            root->left->val = val;
            root->left->left = NULL;
            root->left->right = NULL;
        }
        else
        {
            dfs(root->left, val);
        }
    }
}

struct TreeNode* insertIntoBST(struct TreeNode* root, int val)
{
    if(!root)
    {
        root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        root->left = NULL;
        root->right = NULL;
        root->val = val;
        return root;
    }
    dfs(root, val);
    return root;
}

![Z08G_KN_4GTD1`J_3NC0__F.png](https://i.loli.net/2020/09/30/EUIqglNFiRvJCoz.png)

0x07. 填充每个节点的下一个右侧节点指针

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

示例：

image.png

输入：{“$id”:”1”,”left”:{“$id”:”2”,”left”:{“$id”:”3”,”left”:null,”next”:null,”right”:null,”val”:4},”next”:null,”right”:{“$id”:”4”,”left”:null,”next”:null,”right”:null,”val”:5},”val”:2},”next”:null,”right”:{“$id”:”5”,”left”:{“$id”:”6”,”left”:null,”next”:null,”right”:null,”val”:6},”next”:null,”right”:{“$id”:”7”,”left”:null,”next”:null,”right”:null,”val”:7},”val”:3},”val”:1}

输出：{“$id”:”1”,”left”:{“$id”:”2”,”left”:{“$id”:”3”,”left”:null,”next”:{“$id”:”4”,”left”:null,”next”:{“$id”:”5”,”left”:null,”next”:{“$id”:”6”,”left”:null,”next”:null,”right”:null,”val”:7},”right”:null,”val”:6},”right”:null,”val”:5},”right”:null,”val”:4},”next”:{“$id”:”7”,”left”:{“$ref”:”5”},”next”:null,”right”:{“$ref”:”6”},”val”:3},”right”:{“$ref”:”4”},”val”:2},”next”:null,”right”:{“$ref”:”7”},”val”:1}

解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。

提示：

你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

注：本题和2020.9.28的每日一题几乎完全一样

解法一：层次遍历

我们考虑到当我们填充next指针将每一层的结点都连接起来后，该层所有结点便构成了一个单向链表，我们可以通过遍历每一层的链表来构造下一层的链表

大致过程如下图

BD12E33FCF6E3B97FC6DB3AF5B645CF2.png

时间复杂度：

由于每个结点都要遍历一次，故时间复杂度为O(N)

空间复杂度：

由于没有使用到额外的空间，故空间复杂度为O(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
/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *left;
 *     struct Node *right;
 *     struct Node *next;
 * };
 */

struct Node * last_node, *next_start;

void connectList(struct Node * node)
{
    if(last_node)
    {
        last_node->next = node;
    }
    if(!next_start)
    {
        next_start = node;
    }
    last_node = node;
}

struct Node* connect(struct Node* root) 
{
	if(!root)
        return NULL;
    struct Node *start = root;
    while(start)
    {
        last_node = NULL, next_start = NULL;
        while(start)
        {
            if(start->left)
                connectList(start->left);
            if(start->right)
                connectList(start->right);
            start = start->next;
        }
        start = next_start;
    }
    return root;
}

image.png

0x03.难度：困难

0x00. 冗余连接 II

在本问题中，有根树指满足以下条件的有向图。该树只有一个根节点，所有其他节点都是该根节点的后继。每一个节点只有一个父节点，除了根节点没有父节点。

输入一个有向图，该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组。 每一个边 的元素是一对 [u, v]，用以表示有向图中连接顶点 u 和顶点 v 的边，其中 u 是 v 的一个父节点。

返回一条能删除的边，使得剩下的图是有N个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。

示例 1:

输入: [[1,2], [1,3], [2,3]]
输出: [2,3]
解释: 给定的有向图如下:
1
/
v v
2–>3
示例 2:

输入: [[1,2], [2,3], [3,4], [4,1], [1,5]]
输出: [4,1]
解释: 给定的有向图如下:
5 <- 1 -> 2
^ |
| v
4 <- 3
注意:

二维数组大小的在3到1000范围内。
二维数组中的每个整数在1到N之间，其中 N 是二维数组的大小。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/redundant-connection-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

注：该题为2020.9.17的每日一题

解法：并查集

半夜三点多把前置题：684. 冗余连接给做了，感觉稍微有了点头绪，其实还是啥都不知道…

晚上大概想清楚了，同样是采用并查集的思想，不过考虑到该图为有向图，同时题目给定的图必定有且仅有一条多余的边使得该图无法成为一颗树

可能存在如下情况：

  • 一个节点的入度大于等于2（存在两个及以上父结点，本题数据构造保证只可能存在两个父结点的情况）
  • 图中存在回路
  • 以上两种情况同时存在

如下图所示（字丑见谅QwQ）：

33A2C56517F4926A49A4C03363AECFD0.png

故我们很容易（并不Or2）能够得到解开这道题的算法：

  • 将每一个结点初始化为一棵单独的树，其父结点初始化为自身
  • 使用两个数组分别保存每个结点的父结点与所属的树的根结点
  • 遍历每一条边，重新记录下每个结点的父结点与根节点
  • 当一个结点的入度大于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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 /**
 * Note: The returned array must be malloced, assume caller calls free().
 */

int * ancestors;//（并查集）记录每个节点的根结点
int * parent;//记录每个节点的父结点

int find_x(int x)//查找该结点所属树的根结点
{
    return x == ancestors[x] ? x : (ancestors[x] = find_x(ancestors[x]));//路径压缩
}

void union_ancestor(int a, int b)
{
    ancestors[find_x(a)] = find_x(b);//将两棵树合并为一棵树
}

int* findRedundantDirectedConnection(int** edges, int edgesSize, int* edgesColSize, int* returnSize)
{    
    ancestors = (int*)malloc(sizeof(int)*(edgesSize+5));
    parent = (int*)malloc(sizeof(int)*(edgesSize+5));

    for(int i=1;i<=edgesSize;i++)
    {
        parent[i] = ancestors[i] = i;//初始化每个结点为单独的一棵树（并查集），结点的父结点标记为自身
    }
	//conflict：可能存在争议的边
    //circle：可能形成回路的边
    int start, end, a_start, a_end, conflict = -1, circle = -1;

    for(int i=0;i<edgesSize;i++)
    {
        start = edges[i][0];
        end = edges[i][1];
        a_start = find_x(start);
        a_end = find_x(end);
        if(parent[end] != end)//该条边的尾结点已经与其他结点相连（即加上这条边后入度大于1）
        {
            conflict = i;//记录该条边为争议边
        }
        else
        {
            parent[end] = start;
            if(a_start == a_end)
            {
                circle = i;//该条边两结点的根结点相同，可能形成回路
            }
            else
            {
                union_ancestor(start, end);//将两棵树合并为一棵树（并查集）
            }
        }
    }

    int *ret = (int*)malloc(sizeof(int)*2);
    *returnSize = 2;
    if(conflict<0)//不存在争议边，只存在形成回路的边
    {
        ret[0] = edges[circle][0];
        ret[1] = edges[circle][1];
        return ret;
    }
    else//存在争议边
    {
        if(circle>0)//同时存在回路边
        {
            ret[0] = parent[edges[conflict][1]];
            ret[1] = edges[conflict][1];
            return ret;
        }
        else
        {
            ret[0] = edges[conflict][0];
            ret[1] = edges[conflict][1];
            return ret;
        }
    }
    return ret;
}

image.png

0x01. 监控二叉树

给定一个二叉树，我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

示例 1：

image.png

输入：[0,0,null,0,0]
输出：1
解释：如图所示，一台摄像头足以监控所有节点。
示例 2：

image.png

输入：[0,0,null,0,null,0,null,null,0]
输出：2
解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。

提示：

给定树的节点数的范围是 [1, 1000]。
每个节点的值都是 0。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-cameras
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

该题为2020.9.22的每日一题

仔细想想，对于一个结点是否需要安装摄像头，其实是由其子树的状态来决定的，那么我们可以使用动态规划算法

解法：递归 + 深度优先搜索（DFS） + 动态规划（DP）

大概如下图所示：
image.png

我们考虑有以下几种情况：

  • 当一个结点的左或右子树没有被摄像头覆盖上时，这个结点必须要安装一个摄像头来监测其左或右子树，定义为状态码STATUS_CAMERA
  • 当一个结点的左右子树都已经被摄像头覆盖上时，为了实现摄像头数量的最小化，需要在该结点的父结点放置摄像头，即在回到父结点前该结点都是未被覆盖的，定义为状态码STATUS_UNCOVERED
  • 当一个结点的左右子树中存在摄像头，则该结点肯定是被覆盖了的，定义为状态码STATUS_COVERED
  • 对于结点为NULL的情况，我们可以默认他是被覆盖了的结点，即定义为状态码STATUS_COVERED

同时，我们还需要对这棵树的根节点做一次单独的检测，以确定是否要在其上放置摄像头

为了方便判定，我们将STATUS_CAMERA设置为状态码中值相对大的一个

构造代码如下：

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

/*
 * status code
 * 0: waiting for pwn
 * 1: has been pwn
 * 2: camara here
 *-1: inner error, just a placeholder in fact
 */
#define STATUS_UNCOVERED 0
#define STATUS_COVERED 1
#define STATUS_CAMERA 2
#define STATUS_ERROR -1

int minCameraCover(struct TreeNode* root) 
{
    int amounts=0;//amounts of camera

    //add a camera to the root if status of root is 0
    if(dfs(root,&amounts) == STATUS_UNCOVERED)
        amounts++;
    return amounts;
}

int dfs(struct TreeNode* root, int * amounts)
{
    //NULL pointer signed as status 1
    if(!root)
        return STATUS_COVERED;

    //get the status of left and right node
    int left = dfs(root->left, amounts);
    int right = dfs(root->right, amounts);

    //if one of both uncovered yet, a camera is needed
    if(left == STATUS_UNCOVERED || right == STATUS_UNCOVERED)
    {
        (*amounts)++;
        return STATUS_CAMERA;
    }

    //if both are covered, father's of root may need a camera
    if(left == STATUS_COVERED && right == STATUS_COVERED)
        return STATUS_UNCOVERED;
    
    //if there's at least one camera in both childs, the root is covered
    if(left + right > STATUS_CAMERA)
        return STATUS_COVERED;
    
    //error code(not used)
    return STATUS_ERROR;
}

EE8895_CCLKZDA_OPW4_FT1.png

Welcome to my other publishing channels