从二叉树的节点 A 出发,可以向上或者向下走,但沿途的节点只能经过一次,当到达节点 B 时,路径上的节点数叫作 A 到 B 的距离。
现在给出一棵二叉树,求整棵树上每对节点之间的最大距离。
第一行输入两个整数 n 和 root,n 表示二叉树的总节点个数,root 表示二叉树的根节点。
以下 n 行每行三个整数 fa,lch,rch,表示 fa 的左儿子为 lch,右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子,rch同理)
最后一行为节点 o1 和 o2。
输出一个整数表示答案。
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; }
#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; }
#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; }
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); } }
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; } }
/** * 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 ; }
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)
#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; }
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; } }