二叉树节点之间的距离

深藏阁楼爱情的钟 2023-07-24 03:16 9阅读 0赞

**题目描述**

对二叉树，计算任意两个结点的最短路径长度。

**输入**

第一行输入测试数据组数 T 第二行输入 n , m 。 n 代表结点的个数， m 代表要查询的数据组数。 接下来 n 行，每行输入两个数，代表1~ n 结点的孩子结点，如果没有孩子结点则输入-1，根节点为1。 接下来 m 行，每行输入两个数，代表要查询的两个结点。

**输出**

每组测试数据输出 m 行，代表查询的两个结点之间的最短路径长度。

**测试样例  
输入**

1
    8 4
    2 3
    4 5
    6 -1
    -1 -1
    -1 7
    -1 -1
    8 -1
    -1 -1
    1 6
    4 6
    4 5
    8 1

**输出**

2
    4
    2
    4

#include<bits/stdc++.h>
    using namespace std;
    int fa[1005];
    int main() { 
    	int T,m,n;
    	int a,b;
    	cin>>T;
    	while(T--) { 
    		memset(fa,0,sizeof(fa));
    		cin>>n>>m;
    		for(int i=1;i<=n;i++){ 
    			cin>>a>>b;
    			if(a!=-1){ 
    				fa[a]=i;
    			}
    			if(b!=-1){ 
    				fa[b]=i;
    			}
    		}
    		while(m--){ 
    			cin>>a>>b;
    			stack<int >s1,s2;
    			while(a){ 
    				s1.push(a);
    				a=fa[a];
    			}
    			while(b){ 
    				s2.push(b);
    				b=fa[b];
    			}
    			while(!s1.empty()&&!s2.empty()&&s1.top()==s2.top()){ 
    				s1.pop();
    				s2.pop();
    			}
    			cout<<s1.size()+s2.size()<<endl;
    		}
    	}
    }

发表评论取消回复

表情：

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

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

相关阅读

相关二叉树——222. 完全二叉树的节点个数

1 题目描述给你一棵完全二叉树的根节点 root ，求出该树的节点个数。完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到

我会带着你远行/ 2023年10月08日 16:12/ 0 赞/ 18 阅读

相关二叉树中所有距离为K的节点（DFS+BFS）

二叉树中所有距离为K的节点（DFS+BFS）问题： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_

谁借莪１个温暖的怀抱￠/ 2023年10月06日 14:02/ 0 赞/ 18 阅读

相关二叉树节点之间的距离

题目描述对二叉树，计算任意两个结点的最短路径长度。输入第一行输入测试数据组数 T 第二行输入 n , m 。 n 代表结点的个数， m 代表要查询的数据组数。接下

深藏阁楼爱情的钟/ 2023年07月24日 03:16/ 0 赞/ 10 阅读

相关二叉树祖先节点_二叉树的祖先

二叉树祖先节点 Problem statement: 问题陈述： Given a Binary Tree and a target key, write a functi

一时失言乱红尘/ 2023年03月05日 09:55/ 0 赞/ 11 阅读

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

相关二叉树应用_二叉树的下一个节点

题目：给定一个二叉树和其中的一个节点，找出中序遍历的下一个节点。树中的节点除了有指向左右节点的两个指针之外，还有一个指向父节点的指针。分析：对于这个问题分情况讨论，1、如

淡淡的烟草味﹌/ 2022年05月22日 04:07/ 0 赞/ 249 阅读