java - 如何找到二叉树的直径？

Question

public class Diameter {
    
    // Klasse BinaryTree nicht modifizieren!
    public static class BinaryTree {
        int value;
        BinaryTree left;
        BinaryTree right;

        BinaryTree(int value) {
            this(value, null, null);
        }

        BinaryTree(int value, BinaryTree left, BinaryTree right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    public static int diameter(BinaryTree tree) {
        return 0;
    }

    public static void main(String[] args) {
        case1();
        case2();
        case3();
        case4();
        case5();
        case6();
        case7();
    }

    // Testfälle nicht modifizieren!
    public static void case1() {
        BinaryTree root = new BinaryTree(1,
                new BinaryTree(3,
                        new BinaryTree(7,
                                new BinaryTree(8,
                                        new BinaryTree(9),
                                        null),
                                null),
                        new BinaryTree(4,
                                null,
                                new BinaryTree(5,
                                        null,
                                        new BinaryTree(6)))),
                new BinaryTree(2)
        );
        System.out.println("Case 1: Solution should be 6 -- " + diameter(root));
    }
    
    public static void case2() {
        BinaryTree root = new BinaryTree(1);
        System.out.println("Case 2: Solution should be 0 -- " + diameter(root));
    }
    
    public static void case3() {
        BinaryTree root = new BinaryTree(1,
                new BinaryTree(2),
                null);
        System.out.println("Case 3: Solution should be 1 -- " + diameter(root));
    }
    
    public static void case4() {
        BinaryTree root = new BinaryTree(1,
                new BinaryTree(2),
                new BinaryTree(3));
        System.out.println("Case 4: Solution should be 2 -- " + diameter(root));
    }
    
    public static void case5() {
        BinaryTree root = new BinaryTree(1,
                new BinaryTree(2,
                        new BinaryTree(4),
                        null),
                new BinaryTree(3));
        System.out.println("Case 5: Solution should be 3 -- " + diameter(root));
    }

    public static void case6() {
        BinaryTree root = new BinaryTree(1,
                new BinaryTree(2,
                        new BinaryTree(3,
                                new BinaryTree(4,
                                        new BinaryTree(5,
                                                new BinaryTree(6,
                                                        null,
                                                        new BinaryTree(7)),
                                                null),
                                        null),
                                null),
                        null),
                null);
        System.out.println("Case 6: Solution should be 6 -- " + diameter(root));
    }

    public static void case7() {
        System.out.println("Case 7: Solution should be 0 -- " + diameter(null));
    }

}

我必须编程二叉树的直径是二叉树中最长的路径。路径的定义方式与图形相同。请注意，路径不一定要经过根。

在 Diameter 类中编写一个直径函数，该函数获取二叉树并返回树的直径。

每个节点由一个整数值、一个左孩子left和一个右孩子right组成。每个孩子要么再次是一个节点，要么为空

如何在我的程序中实现它？我的想法是：

public int diameter (Node root)
{
    if (root == null) return 0;
    else return Math.max (
        diameter (root.left), 
        Math.max (
            diameter (root.right),
            height (root.left) + height (root.right) + 1));
}

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

标签： javatree

Answer 1

我们可以进行深度优先遍历并增加每个级别的高度。并从左侧或右侧选择最大值。但我们也不断跟踪left+right并选择最大的一个。

public static int max = 0;
public static int diameter(BinaryTree root, int height) {
    if (root == null) return height-1;

    int left = diameter(root.left, height + 1);
    int right = diameter(root.right, height + 1);
        
    int diameter = left+right-height*2; 
    max = max < diameter ? diameter : max;
        
    return Math.max(left,right);
}

这样称呼它：

max=0;
diameter(root,0);