二叉树的直径和最大距离问题

二叉树的直径和最大距离问题

作者：Grey

原文地址：

博客园：二叉树的直径和最大距离问题

CSDN：二叉树的直径和最大距离问题

二叉树的直径

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径（边）长度中的最大值。

题目链接：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;         }     }  } 

更多

算法和数据结构笔记