0

我有两种方法可以在 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;
        }


    }
4

4 回答 4

2

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

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

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

编辑：您也可以int[2]按照长庚的建议返回一个数组；这仅取决于您发现在语义上更合适的内容。就个人而言，我会选择类似的东西MinMax（Java 并没有真正的标准类来表示值范围），加上将输出参数传递给函数可以节省对象分配，如果这很重要的话。

于 2013-11-06T02:25:58.873 回答
1

您对 Big(O) 的断言是不正确的。在您的实现中，您需要访问树中的每个节点，因此时间复杂度为O(n).

级别顺序树遍历可以一次性给出答案，但您需要两个队列才能正确执行此操作。

public int[] findMinMax(Node node) {
    Queue<Node> currentLevel = new LinkedList<Node>();
    Queue<Node> nextLevel = new LinkedList<Node>();

    currentLevel.offer(node);
    int currentHeight = 1;

    int[] result = new int[]{Integer.MAX_VALUE, Integer.MIN_VALUE};
    while (!currentLevel.isEmpty() || !nextLevel.isEmpty()) {

        if (currentLevel.isEmpty()) {
            currentHeight += 1;
            Queue<Node> tmp = nextLevel;
            nextLevel = currentLevel;
            currentLevel = tmp;
        }

        node = currentLevel.poll();
        if (node.left != null) {
            nextLevel.offer(node.left);
        }
        if (node.right != null) {
            nextLevel.offer(node.right);
        }
        if (node.left == null && node.right == null) {
            result[0] = Math.min(result[0], currentHeight);
        }
    }

    result[1] = currentHeight;

    return result;


}

这么一说，平时真的不值得。递归解决方案更容易编写和理解。

于 2013-11-06T02:40:15.840 回答
0

您总是可以在每个节点上有两个属性，显示节点的最小和最大高度。 

  this.max = Math.max(this.left.max,this.right.max) + 1 ; 
  this.min = Math.min(this.left.min,this.right.min) + 1;
于 2013-11-06T02:18:21.590 回答
0

公共类 MinMax {

public void printMinMaxNumbers(int[] nums){
    int min = nums[0];
    int max = nums[1];
    for(int n:nums){
        if(n < min){
            min = n;
        } else if(n > max){
            max = n;
        }
    }
    System.out.println("Minimum Number: "+min);
    System.out.println("Maximum Number: "+max);
}

public static void main(String a[]){
    int num[] = {5,34,78,21,79,12,97,23};
    MinMax tmn = new MinMax();
    tmn.printMinMaxNumbers(num);
}

}

于 2015-07-09T19:12:42.047 回答