Leetcode 834：树中距离之和（超详细的解法！！！）

Leetcode 834：树中距离之和（超详细的解法！！！）

给定一个无向、连通的树。树中有 N 个标记为 0...N-1 的节点以及 N-1 条边 。 第 i 条边连接节点 edges[i][0] 和 edges[i][1] 。 返回一个表示节点 i 与其他所有节点距离之和的列表 ans。

示例 1

说明: 1 <= N <= 10000

解题思路

这个问题很难，首相可以想到的一个解法是求得每个节点到其他节点的路径和，这个算法的时间复杂度是O...

N叉树的前序遍历

给定一个N叉树，返回其节点值的前序遍历。 例如，给定一个 3叉树 : 返回其前序遍历: [1,3,5,6,2,4]。 说明: 递归法很简单，你可以使用迭代法完成此题吗?

思路：

• 解法一：采用递归的思想遍历n叉树。
• 解法二：采用非递归的思想遍历n叉树，使用辅助数据结构Stack。

N叉树的最大深度

给定一个N叉树，找到其最大深度。 最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。 例如，给定一个 3叉树 : 我们应返回其最大深度，3。 说明: 树的深度不会超过 1000。 树的节点总不会超过 5000。

思路：

• 广度优先遍历树，计算树的层数，最大层数就是树最大深度。

二叉搜索树的恢复

二叉搜索树中的两个节点被错误地交换。 请在不改变其结构的情况下，恢复这棵树。

示例 1

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

示例 2

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

使用 O(n) 空间复杂度的解法很容易实现,代码如下

图的冗余连接

is the size of the input array. 思路与解法 方法一 从题目中可知，我们需要从一个图中找出一条多余的边，使得去掉该边之后，剩余的节点和边形成一棵树（连通且无环）。题目...]=v，即将y和v直接相连。经过这样的处理，可以得知，一个连通分量的所有节点最终只存在一个父亲节点（此节点的父亲节点即为自身）。可以思考这样的情况：如果两个节点m、n经过边edge相连，查找m和n的父亲节点