java - 在Java中二叉树的遍历中得到一棵树的最小和最大高度？

我有两种方法来获取Java中二叉树的最小和最大高度。但是我两次遍历了根两次。每个都是log n in Big(O)。有没有一种方法可以在相同的遍历中同时计算最小值和最大值，并作为具有两个分别对应于最小值和最大值的索引的数组返回。

这是我的方法

public static int minHeight(Node root){
            if (root==null) return -1;
            return 1+Math.min(minHeight(root.left), minHeight(root.right));
        }

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

        }

class Node {
        Node left;
        Node right;
        int data;

        public Node(int c){
            this(c, null, null);
        }
        public Node(int c,Node left, Node right) {
            this.data = c;
            this.left=left;
            this.right=right;
        }


    }

最佳答案

只需一遍计算高度，然后就可以跟踪最小和最大。您的困惑在于您的函数返回一个值，但实际上您需要确定一对值。因此，您可以传入一个对象，该对象具有一个可以存储结果的字段，并通过该字段而不是通过函数的返回值返回结果：

class MinMax {
    public int min;
    public int max;
}

void computeMinMaxHeight (Node root, MinMax minmax) {
    // update the fields of minmax accordingly
}

初始化MinMax字段的便捷方法可能是：

class MinMax {
    public int min = Integer.MAX_VALUE;
    public int max = Integer.MIN_VALUE;
}

或添加一些指示未初始化的标志，以便正确填写第一项的值。

编辑：您还可以按照Changgeng的建议返回一个int[2]数组；这取决于您在语义上是否更合适。就个人而言，我会选择类似MinMax的东西（Java确实没有用于表示值范围的标准类），再加上将输出参数传递给函数可以节省对象分配，如果那很重要的话。

关于java - 在Java中二叉树的遍历中得到一棵树的最小和最大高度？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19802780/