今天中午的时候有人问了我一个问题:求二叉树中节点的最大距离。这是《编程之美》上的一个问题。
花了一中午的时间总算解决了这个问题,有一点是很明确的:如果把树看做是一个图的话,它必然是连通的,任一节点总有路径到其他任何节点,这个题目就是求这样最长的一条路径。距离最大的两个节点可能是一个在左子树,一个在右子树,也可能是在一个子树上。下面的图展示了这两种情况
我试着把这个问题转化一下:树中的每一个节点都是一颗子树的根,对于这棵子树而言,它左子树的高度是Lm,右子树的高度是Rm,求所有子树中(Lm + Rm)的最大值是多少?(虽然不知道这样的问题在实际生产中是否有意义,也许有吧),还是用图比较直观。
在图上标出了每个节点左子树的长度和右子树的长度,叶子节点的左右子树长度都是0。每个节点左子树的长度是左孩子的左子树长度和左孩子右子树长度中较长的那个再加1,,这句话比较绕,但是好理解,比如A->Lm = Max(B->Lm,B->Rm) + 1,这样很明了了吧。有了上面的信息之后,我们可以计算每棵子树的(Lm + Rm),其中最大者就是结果。由于树的定义是递归的,所以用递归的方式更容易编程。
算法步骤:
(1)初始化二叉树,并将每个节点Lm和Rm初始化为0,定义二叉树中节点的最大距离Max = -1
(2)为了计算一个节点的Lm和Rm,需要采用后序遍历策略,递归的计算出它左孩子Left的Lm,Rm,Lm = max(Left->Lm + Left->Rm) + 1;和右孩子Right的Lm,Rm,Rm = max(Right->Lm,Right->Rm) + 1;
(3)对于每一个节点,计算Lm + Rm,如果其值大于Max,则Max = Lm + Rm,最后Max就是最大距离。
树节点的声明如下:
typedef struct TreeNode *Position;
typedef Position Tree;
struct TreeNode {
int element;
Position left;
Position right;
int lm;
int rm;
};
static int max = -1;//保存最远的距离
实际算法如下:
/*计算一棵树中,距离最远两个节点之间的距离*/
/*具体算法:每个节点有两个域分别用来保存它左子树的最大高度lm和右子树的最大高度rm
*将lm + rm与当前已知最远的距离相比较,如果大于max,则更新Max的值
*/
int maxDist(Tree root) {
//如果树是空的,则返回0
if(root == NULL)
return 0;
if(root->left != NULL) {
root->lm = maxDist(root->left) + 1;
}
if(root->right != NULL)
root->rm = maxDist(root->right) + 1;
//如果以该节点为根的子树中有最大的距离,那就更新最大距离
int sum = root->rm + root->lm;
if(sum > max) {
max = sum;
}
return root->rm > root->lm ? root->rm : root->lm;
}
上面的代码对每个节点只处理一次,所以时间复杂度是O(N),N是节点个数。
转载请注明:喻红叶《求二叉树中节点的最大距离》
分享到:
相关推荐
求二叉树节点的最大距离求二叉树节点的最大距离求二叉树节点的最大距离
求二叉树中任意两个节点的最大距离,。。用C++在VC下实现
c语言实现寻找一个二叉树中距离最大的两个节点
直径或宽度(树中任意两个节点之间的最长距离) 二叉树节点的组成部分 它保存的数据类型,例如Int或String等 指向左子节点的指针 指向右子节点的指针 常见操作 遍历 插入 删除 二叉树节点 class BinaryTreeNode <...
给定一颗二叉树的头节点,任何两个节点之间都存在距离,返回整颗二叉树的最大距离 给定一颗二叉树的头节点,返回这颗二叉树的最大搜索子树的节点数 给定一棵二叉树头节点,返回其最大二叉搜索子树的头节
二叉树中两个节点之间的距离 4 二叉树的中序后继 5 二叉树的有序后继前驱 5 反转树 6 二叉树中最大的BST 7 恢复二叉树 8 二叉树的螺旋顺序 9 检查是否为 BST 10 层序二叉树 11 有序二叉树 12 预购二叉树 13 后序...
leetcode 530 leetcode 二叉树 100.相同的树 105.从前序与中序遍历序列构造二叉树 106.从中序与后序遍历序列构造二叉树 107.二叉树的层序遍历II 111.二叉树的最小深度 ...783.二叉搜索树节点最小距离
5.4.4 满二叉树添加指向右边节点的指针 5.4.5 根节点到叶结点的所有路径代表的数字之和 6. 排序 6.1 合并两个有序数组到其中一个数组 6.2 合并两个有序链表 6.3 合并K个有序链表 6.4 使用插入排序来排序链表 6.5 ...
045-二叉树中的最大路径和 046-最长连续序列 047-只出现一次的数字 048-单词拆分 049-环形链表 050-环形链表II 051-LRU缓存机制 052-最小栈 053-乘积最大子数组 054-排序链表 055-相交链表 056-合并K个升序数组 057-...
数学问题: 1.精度计算——大数阶 乘 ...4.Floyd 算法求每对节点 间最短路径 排序/查找: 1.快速排序 2.希尔排序 3.选择法排序 4.二分查找 数据结构: 1.顺序队列 2.顺序栈 3.链表 4.链栈 5.二叉树
二叉树中所有节点距离 K , 第一个坏版本, 恢复二叉搜索树, 尝试 实现 Trie(前缀树), 替换词, 链表 回文链表 添加两个数字, 反向链表, 从列表末尾删除第 N 个节点, 堆栈 基本计算器, 子阵列最小值的总和 ...
树中距离之和 颜色分类 转字符串 环形链表 环形链表 II 分割等和子集 二叉搜索树的最小绝对差 两两交换链表中的节点 查找常用字符 填充每个节点的下一个右侧节点指针 有序数组的平方 N皇后 II 删除链表的倒数第N个...
leetcode 530 Golang leetcode 练习记录 ...二叉树中的第二个最小节点 树 简单的 最长单值路径 树 简单的 在二叉搜索树中搜索 树 简单的 BST节点之间的最小距离 树 简单的 叶相似树 树 简单的 递增顺序
4.Floyd算法求每对节点间最短路径 排序/查找: 1.快速排序 2.希尔排序 3.选择法排序 4.二分查找 数据结构: 1.顺序队列 2.顺序栈 3.链表 4.链栈 5.二叉树 ...
求数组中个数最多的数字 判断单链表是否有环 二分搜索 缺失的数字 包含min函数的栈 合并两个递增排序的链表 连续子序列的最大和 替换空格 二维数组中的查找 从尾到头打印链表 重建二叉树(用前序和中序构建) 从上到下...
在每个节点中填充下一个右指针 Pow(x, n) 同一棵树 子集 根到叶数求和 成对交换节点 对称树 有效回文 验证二叉搜索树 恢复 IP 地址 组合 交错字符串(dp 是最好的) 组合和II 电话号码的字母组合 词搜索 从中序和...
删除链表中的节点 删除最外层的括号 唯一摩斯密码词 翻转图像 合并二叉树 汉明距离 翻转二叉树 高度检查器 二叉树的最大深度 有序数组的平方 增减字符串匹配 二叉搜索树中的搜索 N叉树的后序遍历 N叉树的前序遍历 ...
针对分解支持向量机具有测试时间短、结构难以确定的特点,利用粒子群算法,依据最大间隔距离原则优化层次支持向量机模型,使每个节点的支持向量机具有最大分类间隔,减少了误差积累,从而优化了多级二叉树结构的SVM,...