java - 在Java中一次遍历二叉树时获取树的最小和最大高度？

Question

我有两种方法来获取 Java 中二叉树的最小和最大高度。但我对根进行了两次遍历。每个都是 Big(O) 中的 log n。有没有办法在同一次遍历中计算最小值和最大值，并以数组形式返回，其中两个索引对应于最小值和最大值。

这是我的方法

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;
        }


    }

Answer 1

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

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 实际上没有一个用于表示值范围的标准类)，再加上将输出参数传递给函数可以节省对象分配，如果是的话意义重大。