二叉樹的直徑和最大距離問題
二叉樹的直徑和最大距離問題
作者：Grey
原文地址：
二叉樹的直徑
給定一棵二叉樹，你需要計算它的直徑長度。一棵二叉樹的直徑長度是任意兩個結點路徑（邊）長度中的最大值。
題目鏈接：LeetCode 543. Diameter of Binary Tree
主要思路：
定義如下數據結構
public static class Info {
public int maxHeight; // 從當前節點插到最底部最大高度
public int max; // 當前樹的直徑
public Info(int max, int maxHeight) {
this.max = max;
this.maxHeight = maxHeight;
}
}
其中max為當前樹的直徑，maxHeight為從當前節點插到最底部的最大高度；
假設以 head 為頭的二叉樹，左樹為 left，右樹為 right，
接下來開始整理以 head 為頭的二叉樹直徑的可能性：
可能性1，以 head 為頭的二叉樹的直徑可能只來自做左樹，即: left.max。
可能性2，以 head 為頭的二叉樹的直徑可能只來自做左樹，即: right.max。
可能性3，以 head 為頭的二叉樹的直徑可能只來自做左樹，即: right.maxHeight + left.maxHeight。
所以，以 head 為頭的二叉樹直徑最終為上述三種可能性的最大值，即
Math.max(Math.max(right.max,left.max),right.maxHeight + left.maxHeight);
接下來整理以 head 為頭，能插到最底部的最大高度的可能性：
可能性1，head 節點能插入到左樹最底部的最大高度是left.maxHeight + 1，
可能性2，head 節點能插入到右樹最底部的最大高度是right.maxHeight + 1，
以上兩種可能性求最大值即可，即
Math.max(left.maxHeight, right.maxHeight) + 1
完整程式碼如下
class Solution {
public static int diameterOfBinaryTree(TreeNode head) {
if (head == null) {
return 0;
}
return process(head).max;
}
public static class Info {
public int maxHeight; // 從當前節點插到最底部最大高度
public int max; // 當前樹的直徑長度
public Info(int max, int maxHeight) {
this.max = max;
this.maxHeight = maxHeight;
}
}
private static Info process(TreeNode head) {
if (head == null) {
return new Info(0, 0);
}
Info left = process(head.left);
Info right = process(head.right);
int max = Math.max(left.maxHeight + right.maxHeight, Math.max(left.max, right.max));
int maxHeight = Math.max(left.maxHeight, right.maxHeight) + 1;
return new Info(max, maxHeight);
}
}
二叉樹節點間的最大距離問題
題目鏈接: 牛客：二叉樹節點間的最大距離問題
主要思路：
這個問題和上述問題類似，只不過在求上述問題的時候，我們定義兩個節點的距離是以邊為準，而本問題是以兩個節點之間的節點數量為準，而兩個節點之間
邊的數量 + 1 = 節點數量
所以我們可以基於上述的問題的程式碼，方便得到本題的程式碼，核心程式碼如下
public static Info process(TreeNode head) {
if (head == null) {
return new Info(0, 0);
}
Info left = process(head.left);
Info right = process(head.right);
int max = Math.max(left.maxHeight + right.maxHeight + 1, Math.max(left.max, right.max));
int maxHeight = Math.max(left.maxHeight, right.maxHeight) + 1;
return new Info(max, maxHeight);
}
和上述問題唯一不同的程式碼就是如下邏輯，上述問題是
int max = Math.max(left.maxHeight + right.maxHeight, Math.max(left.max, right.max));
而本題的邏輯是
int max = Math.max(left.maxHeight + right.maxHeight + 1, Math.max(left.max, right.max));
即邊的數量 + 1 = 節點數量
完整程式碼如下：
import java.util.HashMap;
import java.util.Scanner;
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, TreeNode> map = new HashMap<>();
TreeNode root = new TreeNode();
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]);
TreeNode curNode = map.get(faVal);
if (lchVal != 0) {
TreeNode lch = new TreeNode();
curNode.left = lch;
map.put(lchVal, lch);
}
if (rchVal != 0) {
TreeNode rch = new TreeNode();
curNode.right = rch;
map.put(rchVal, rch);
}
}
Info info = process(root);
System.out.println(info.max);
}
public static Info process(TreeNode head) {
if (head == null) {
return new Info(0, 0);
}
Info left = process(head.left);
Info right = process(head.right);
int max = Math.max(left.maxHeight + right.maxHeight + 1, Math.max(left.max, right.max));
int maxHeight = Math.max(left.maxHeight, right.maxHeight) + 1;
return new Info(max, maxHeight);
}
private static class TreeNode {
int val;
TreeNode left;
TreeNode right;
}
private static class Info {
int maxHeight;
int max;
public Info(int max, int maxHeight) {
this.max = max;
this.maxHeight = maxHeight;
}
}
}
