首页 > 试题广场 >

二叉树节点间的最大距离问题

[编程题]二叉树节点间的最大距离问题
  • 热度指数：2154 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
从二叉树的节点 A 出发，可以向上或者向下走，但沿途的节点只能经过一次，当到达节点 B 时，路径上的节点数叫作 A 到 B 的距离。
现在给出一棵二叉树，求整棵树上每对节点之间的最大距离。

输入描述:
第一行输入两个整数 n 和 root，n 表示二叉树的总节点个数，root 表示二叉树的根节点。
以下 n 行每行三个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子，rch同理)
最后一行为节点 o1 和 o2。


输出描述:
输出一个整数表示答案。
示例1

输入

7 1
1 2 3
2 4 5
4 0 0
5 0 0
3 6 7
6 0 0
7 0 0

输出

5

备注:

算法知识视频讲解
添加回答
勇敢牛牛，不怕困难！头像 勇敢牛牛，不怕困难！ 
#include <stdio.h>
#include <stdlib.h>

typedef int ID;

typedef struct TreeNode {
  ID id;
  struct TreeNode* left;
  struct TreeNode* right;
} TreeNode, *PTNode, *BT;

typedef struct {
  ID id, l_child, r_child;
} TNodeInfo, *INFO;

BT CreateBT(INFO infos, ID root_id) {
  // recursion exit condition
  if (!root_id) return NULL;
  
  BT t = (PTNode) malloc(sizeof(TreeNode));
  if (!t) return NULL;
  
  t->id    = root_id;
  t->left  = CreateBT(infos, infos[root_id].l_child);
  t->right = CreateBT(infos, infos[root_id].r_child);
  return t;
}

// 释放整颗树占用的内存空间，避免内存泄漏！
void DestroyBT(BT t) {
  if (!t) return;
  DestroyBT(t->left);
  DestroyBT(t->right);
  free(t);
}

// 应该算树型DP
int postorder(BT t, int* ans) {
  if (!t) return 0;
  const int l = postorder(t->left, ans);
  const int r = postorder(t->right, ans);
  *ans = fmax(*ans, 1 + l + r);
  return 1 + fmax(l, r);
}

int main(void) {
  int n, root_id;
  fscanf(stdin, "%d %d\n", &n, &root_id);
  
  TNodeInfo infos[n + 1];
  ID fa, l_ch, r_ch;
  while (n--) {
    fscanf(stdin, "%d %d %d", &fa, &l_ch, &r_ch);
    (*(infos + fa)).id = fa;
    (*(infos + fa)).l_child = l_ch;
    (*(infos + fa)).r_child = r_ch;
  }
  
  BT t = CreateBT(infos, root_id);
  int ans = 0;
  postorder(t, &ans);
  return fprintf(stdout, "%d", ans), DestroyBT(t), 0;
}

发表于 2021-07-30 19:39:28 回复(0)
牛客887263087号头像 牛客887263087号 
#include <iostream>
using namespace std;

struct Node{
    int val;
    Node* left;
    Node* right;
    Node(int val_)
        :val(val_),left(nullptr),right(nullptr)
        {}
};

struct ReturnType{
    int height;
    int maxDistance;
};

Node* createTree(){
    int val;
    int left;
    int right;
    cin >> val >> left >> right;
    Node* head = new Node(val);
    if(left != 0)
        head->left = createTree();
    if(right != 0)
        head->right = createTree();
    return head;
}

void deleteTree(Node* head){
    if(head == nullptr)
        return;
    if(head->left != nullptr)
        deleteTree(head->left);
    if(head->right != nullptr)
        deleteTree(head->right);
    delete head;
}

ReturnType getMaxDistance(Node* head){
    if(head == nullptr)
        return {0, 0};
    ReturnType left = getMaxDistance(head->left);
    ReturnType right = getMaxDistance(head->right);
    int height = max(left.height, right.height) + 1;
    int maxDistance = max(left.height + right.height + 1,
                         max(left.maxDistance, right.maxDistance));
    return {height, maxDistance};
}

int main(void){
    int n, rootVal;
    cin >> n >> rootVal;
    Node* root = createTree();
    ReturnType r = getMaxDistance(root);
    cout << r.maxDistance << endl;
    deleteTree(root);
    return 0;
}
求二叉树节点间的最大距离，是有套路的
根据有没有头结点进行分析。
同时我把createTree和deleteTree都要写入，防止内存泄漏。
写错了一个方面
需要得到的信息是高度和最大距离。
发表于 2021-05-29 10:52:47 回复(0)
不是很黑头像 不是很黑 
#include<bits/stdc++.h>
using namespace std;

int maxx=-1;         //保存距离最大值
int v[500000][2];  //保存节点

int Max(int p){    //基本等于求树的高度，在遍历时保存距离最大值
	int l=0,r=0;
	if(v[p][0]!=0)
		l=Max(v[p][0]);
	if(v[p][1]!=0)
		r=Max(v[p][1]);
	if(maxx<l+r+1)
		maxx=l+r+1;
	return (l>r?l:r)+1;
}
int main(){
	int n,root,p;
	cin>>n>>root;
	for(int i=0;i<n;i++)
	{
		cin>>p;
		cin>>v[p][0]>>v[p][1];
	}
	Max(root);
	cout<<maxx;
}

发表于 2020-03-12 14:53:32 回复(1)
Java
pein531头像 pein531
树型DP套路。对于以某个节点为根节点的子树，有如下两种情况：
                                  
  1. 当前节点不参与路径，此时左右子树中最大路径较大的那个就是当前节点不参与路径时的最长路径。如上图红色节点（根节点）的子树中，最长路径就是两个黄色节点经过蓝色节点的路径，并未经过红色节点自身。
  2. 当前节点参与路径，此时最大的路径应该是：左树高+右树高+1（1为当前节点）。如上图中蓝色节点的子树中，最长路径就是两个黄色节点经过自己的那条路径。
这时候对于某个节点而言，只要向左右孩子节点收集信息，就能够计算它的最大路径，需要的信息有：(1) 左子树高度；(2) 右子树高度；(3) 左右孩子的最长路径。根据信息(3)我们可以求得当前节点不参与路径时的最长路径；根据信息(1)和(2)我们可以求得当前节点参与路径时的最长路径。而为了在根节点汇总整棵树的信息，每个节点需要把当前收集到的信息做一个汇总，方便自己的父节点使用：
  1. 计算以当前节点为根节点的子树高度：height=max(left_height, right_height)+1
  2. 以当前节点为根节点的子树所包含的最大路径长度：max(左子树最大路径, 右子树最大路径, 左树高+右树高+1) 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;

class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val) {
        this.val = val;
    }
}

// 信息体结构
class Info {
    public int maxDistance;      // 最大距离
    public int height;           // 树高
    public Info(int maxDistance, int height) {
        this.maxDistance = maxDistance;
        this.height = height;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]), rootVal = Integer.parseInt(params[1]);
        // 构建树
        HashMap<Integer, TreeNode> map = new HashMap<>();
        TreeNode root = new TreeNode(rootVal);
        map.put(rootVal, root);
        for(int i = 0; i < n; i++){
            params = br.readLine().split(" ");
            int val = Integer.parseInt(params[0]);
            int leftVal = Integer.parseInt(params[1]);
            int rightVal = Integer.parseInt(params[2]);
            TreeNode node = map.get(val);
            if(leftVal != 0) {
                node.left = new TreeNode(leftVal);
                map.put(leftVal, node.left);
            }
            if(rightVal != 0) {
                node.right = new TreeNode(rightVal);
                map.put(rightVal, node.right);
            }
        }
        // 树形DP
        Info info = process(root);
        System.out.println(process(root).maxDistance);
    }
    
    private static Info process(TreeNode root) {
        if(root == null)
            return new Info(0, 0);
        Info leftInfo = process(root.left);        // 左树信息
        Info rightInfo = process(root.right);      // 右树信息
        // 经过头节点的路径
        int path1 = leftInfo.height + rightInfo.height + 1;
        // 不经过头结点的路径
        int path2 = Math.max(leftInfo.maxDistance, rightInfo.maxDistance);    // 左右子树中路径大的那个
        return new Info(Math.max(path1, path2), Math.max(leftInfo.height, rightInfo.height) + 1);
    }
}

编辑于 2021-11-18 11:07:34 回复(0)
牛客303394055号头像 牛客303394055号 
import java.lang.Math;
import java.util.Scanner;
import java.util.HashMap;


class Node{
    Node left;
    Node right;
}

class Info{
    int height = 0;
    int maxDistance = 0;
}

public class Main{
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        String firstLine = sc.nextLine();
        String[] s = firstLine.split(" ");
        int n = Integer.valueOf(s[0]);
        int rootVal = Integer.valueOf(s[1]);
        HashMap<Integer, Node> map = new HashMap<>();
        Node root = new Node();
        map.put(rootVal, root);
        
        //构建二叉树
        for(int i=0; i<n; i++){
            String line = sc.nextLine();
            String[] str = line.split(" ");
            int faVal = Integer.valueOf(str[0]);
            int lchVal = Integer.valueOf(str[1]);
            int rchVal = Integer.valueOf(str[2]);
            
            Node curNode = map.get(faVal);
            
            if(lchVal != 0){
                Node lch = new Node();
                curNode.left = lch;
                map.put(lchVal, lch);
            }
            if(rchVal != 0){
                Node rch = new Node();
                curNode.right = rch;
                map.put(rchVal, rch);
            }
        }
        
        Info info = process(root);
        System.out.println(info.maxDistance);
        
        
    }

    public static Info process(Node N){
        Info curInfo = new Info();
        
        if(N == null){
            return curInfo;
        }
        
        Info leftInfo = process(N.left);
        Info rightInfo = process(N.right);
        int dis1 = Math.max(leftInfo.maxDistance, rightInfo.maxDistance);
        int dis2 = leftInfo.height + rightInfo.height + 1;
        curInfo.maxDistance = Math.max(dis1, dis2);
        curInfo.height = Math.max(leftInfo.height, rightInfo.height) + 1;
        
        return curInfo;
    }

}

发表于 2022-05-24 16:20:59 回复(0)
Java
keydous头像 keydous 

        /**
     * 1. 最长距离不路过root，
     * 2. 最长距离路过root
     * @param root
     * @return
     */
    public static int maxDistance(TreeNode root){
        if (root == null){
            return 0 ;
        }
        //每个节点的最大距离分为上述的两种情况
        //这里需要重复的计算节点的高度
        return Math.max(height(root.left)+height(root.right)+1 ,
                Math.max(maxDistance(root.left) , maxDistance(root.right))) ;
    }

    public static int height(TreeNode root){
        if (root == null){
            return 0 ;
        }
        if (root.left == null && root.right == null){
            return 1 ;
        }
        return Math.max(height(root.left) , height(root.right))+1 ;
    }


发表于 2020-07-26 23:29:15 回复(0)
字节bug跳动头像 字节bug跳动 

import sys


def parse(relations, root):
    if relations[root][0] == 0 and  relations[root][1] == 0:
        return 1, 0 # max depth, max range

    left_depth, left_deltas = parse(relations, relations[root][0] ) if relations[root][0] != 0 else [0, 0]
    right_depth, right_deltas = parse(relations, relations[root][1] ) if relations[root][1] != 0 else [0, 0]
    max_depth = max(left_depth, right_depth) + 1
    max_deltas = max([left_deltas, right_deltas, left_depth + right_depth + 1])

    # print('current node', root, 'max_depth, max_deltas', max_depth, max_deltas)
    return max_depth, max_deltas


n, root_index = [int(val) for val in sys.stdin.readline().strip().split()]
relation_array = [[], ] * (n + 1)
for _ in range(0, n):
    idx, lf, rg =  [int(val) for val in sys.stdin.readline().strip().split()]
    relation_array[idx] = [lf, rg]

# print('relation_array', relation_array)
out = parse(relation_array, root_index)[1]
print(out)



发表于 2020-06-15 11:04:34 回复(0)
皮蛋秀柚秋头像 皮蛋秀柚秋 
#include<bits/stdc++.h>
using namespace std;
struct Node{
    int lc;
    int rc;
};
// 注意到最长的那条路径上必定有一个节点是其他所有节点的祖先节点
// 实质就是求树高，在这个过程中顺便求解了答案
pair<int,int> getMaxDistance(vector<Node>& tree,int root)
{
    if(!root) return make_pair(0,0);
    pair<int,int>pl = getMaxDistance(tree,tree[root].lc);
    pair<int,int>pr = getMaxDistance(tree,tree[root].rc);
    int height = max(pl.first,pr.first) + 1;
    int maxDistance = max( pl.first+pr.first+1, max(pl.second,pr.second));
    return make_pair(height,maxDistance);
}
int main()
{
    int n,root;
    cin>>n>>root;
    vector<Node>tree(n+1);
    int p;
    for(int i=0;i<n;++i)
    {
        cin>>p;
        cin>>tree[p].lc>>tree[p].rc;
    }
    cout<<getMaxDistance(tree,root).second<<endl;
}
发表于 2020-02-07 11:49:43 回复(0)
Java
我的一个修仙朋友头像 我的一个修仙朋友 
import java.util.Scanner;

public class Main{
    private static int res = 0;
    public static void main(String[] args){
        Main m = new Main();
        Scanner sc = new Scanner(System.in);
        String firstLine = sc.nextLine();
        String[] s = firstLine.split(" ");
        int n = Integer.valueOf(s[0]);
        int root = Integer.valueOf(s[1]);
        int[][] tree = new int[n][3];
        for(int i = 0;i < n;i++){
            String line = sc.nextLine();
            s = line.split(" ");
            int row = Integer.valueOf(s[0]);
            tree[row - 1][0] = Integer.valueOf(s[0]);
            tree[row - 1][1] = Integer.valueOf(s[1]);
            tree[row - 1][2] = Integer.valueOf(s[2]);
        }
        m.computeCore(tree,root);
        System.out.println(res);
    }

    private int computeCore(int[][] tree,int root){
        if(root == 0) return 0;
        int left = computeCore(tree,tree[root-1][1]);
        int right = computeCore(tree,tree[root-1][2]);
        int depth = 1 + Math.max(left,right);
                res = Math.max(res,1 + left + right);
        return depth;
    }
}

求得每个节点的左子树深度left，右子树深度right，最大距离为所有的max(1+left+right)
编辑于 2019-12-23 15:52:40 回复(0)
C/C++
keepgoing20190801113019头像 keepgoing20190801113019
#include <iostream>
#include <string>
#include <vector>

using namespace std;

long MAX=0;
long height(vector<vector<long>> &tree, long &node)
{
    if (node==0)
        return 0;
   
    long left = height(tree, tree[node][0]);
    long right = height(tree, tree[node][1]);
   
    MAX = (left+right+1)>MAX?(left+right+1):MAX;
    
    return 1+max(left,right);
}

int main(){
    
    long num,root;
    cin>>num>>root;
    long far,lch,rch;
    vector<vector<long>> tree(500001,{0,0});
    for (long i=0; i<num; i++)
    {
        cin>>far>>lch>>rch;
        tree[far][0]=lch;
        tree[far][1]=rch;
    }
    
    height(tree, root);
    cout<<MAX;
    
    return 0;
}
发表于 2019-08-03 21:32:29 回复(0)
提交观点

问题信息

树
上传者：小小
难度：
10条回答 7472浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号