在Java中一次遍历二叉树就能得到树的最小高度和最大高度？

Question

我有两种方法来获取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;
        }


    }

Answer 1

公共类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);
}

}

Answer 2

你所说的大（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;


}

说这句话，正常情况下这真的不值得。递归解决方案更容易编写和理解

Answer 3

每个节点上都可以有两个属性，显示节点的最小高度和最大高度

  this.max = Math.max(this.left.max,this.right.max) + 1 ; 
  this.min = Math.min(this.left.min,this.right.min) + 1;