二元樹的直徑和最大距離問題

作者：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;
        }
    }

}

演演算法和資料結構筆記

二元樹的直徑和最大距離問題

二元樹的直徑和最大距離問題

二元樹的直徑

二元樹節點間的最大距離問題

更多