求二叉树中距离最远的两个叶子节点的距离

短命女 2022-05-30 07:44 208阅读 0赞

问题：

给定一棵二叉树（非二叉检索树），求二叉树中距离最远的两个叶子节点间的距离？其中两个叶子间的距离定义为：F(X,Y) = 从节点X到根节点路径上所有节点数据之和 + 从节点Y到根节点路径上所有节点数据之和 - 从X和Y的第一个祖先节点到根节点路径上所有节点数据之和。

思路：

1，后序遍历每一节点，找出该节点到最右边的距离以及最左边的距离；

2，找到之和最大的即可。

struct TNode
    {
    	int data;
    	TNode * left_child;
    	TNode * right_child;
    }
    
    void FindMax( TNode *pNode, int &max_distance, int &tot_distance )
    {
    	if( pNode == NULL )
    	{	max_distance = 0;
    		tot_distance = 0;
    		return;
    	}
    	else
    	{
    		int left_max_distance;
    		int left_tot_distance;
    		int right_max_distance;
    		int right_tot_distance;
    		FindMax( pNode->left_child, left_max_distance, left_tot_distance);
    		FindMax( pNode->right_child, right_max_distance, right_tot_distance);
    
    		tot_distance = left_max_distance + right_max_distance + pNode->data;
    		max_distance = left_max_distance>right_max_distance?(left_max_distance+pNode->data):(right_max_distance+pNode->data);
    		
    		tot_distance = tot_distance>left_tot_distance?tot_distance:left_tot_distance;
    		tot_distance = tot_distance>right_tot_distance?tot_distance:right_tot_distance;
    	}
    }
    
    main()
    {
    	FindMax( pNode, max_distance, result);
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，208人围观）

还没有评论，来说两句吧...

相关阅读

相关 783. 二叉搜索树节点最小距离

定一个二叉搜索树的根节点 root，返回树中任意两节点的差的最小值。 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shad

￡神魔★判官ぃ/ 2023年03月01日 10:19/ 0 赞/ 89 阅读

相关【每日一题】二叉搜索树节点最小距离

783. 二叉搜索树节点最小距离给你一个二叉搜索树的根节点 root ，返回树中任意两不同节点值之间的最小差值。注意：本题与 530：https

╰+哭是因爲堅強的太久メ/ 2023年01月13日 10:44/ 0 赞/ 171 阅读

相关 LeetCode | 0783. 二叉搜索树节点最小距离【Python】

Problem [LeetCode][] Given a Binary Search Tree (BST) with the root node `root`, ret

比眉伴天荒/ 2023年01月09日 15:37/ 0 赞/ 149 阅读

相关二叉树——好叶子节点对个数，求叶子节点之间的最短距离

给你二叉树的根节点 root 和一个整数 distance 。如果二叉树中两个叶节点之间的最短路径长度小于或者等于 distance ，那它们就可以构成一组好叶子

落日映苍穹つ/ 2022年12月05日 13:48/ 0 赞/ 177 阅读

相关求二叉树叶子节点的最浅深度

下面给出一个例子： ![20151031140526517][] 对于该二叉树而言，叶子节点有C、D两个，C节点的深度为3，D节点的深度为2，那么最浅叶子节点的深度为

梦里梦外;/ 2022年08月09日 15:56/ 0 赞/ 183 阅读

相关【结构之法】二叉树中节点的最大距离

前言：编程之美中的解法并不是最好的，所以这里给出大神的解法。问题：如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，我们姑且定义”距离”为两节点之间边的个

今天药忘吃喽~/ 2022年08月09日 06:59/ 0 赞/ 142 阅读

相关求二叉树中最远的两个节点的距离

求二叉树中最远的两个节点的距离短短的代码中其实涉及到了三道题目： 1. 利用已知序列递归的建一棵二叉树 2. 递归的求一棵树的深度 3. 求二叉树中距离最远的两个节

爱被打了一巴掌/ 2022年07月14日 02:11/ 0 赞/ 154 阅读

相关树的直径（最远距离）

输入数据 5 5 1 2 2 2 4 3 2 5 1 4 5 4 1 3 5 有5个点5条边 ![Center][] 第一次bfs从1号

拼搏现实的明天。/ 2022年06月15日 04:30/ 0 赞/ 168 阅读

相关求二叉树中距离最远的两个叶子节点的距离

问题：给定一棵二叉树（非二叉检索树），求二叉树中距离最远的两个叶子节点间的距离？其中两个叶子间的距离定义为：F(X,Y) = 从节点X到根节点路径上所有节点数据之和 + 从

短命女/ 2022年05月30日 07:44/ 0 赞/ 209 阅读

相关二叉树任意两个结点最长距离

给定一棵二叉树，求出树中两个结点距离的最大值。首先明确距离最大的两个结点出现位置：1，同时在根结点的左子树中；2，同时在根结点的右子树中；3，左右子树中各有

秒速五厘米/ 2022年05月17日 12:56/ 0 赞/ 160 阅读