java - 获取没有函数参数的二叉树的高度

Question

import java.util.Scanner;

public class BinaryTree {

private int info;
private BinaryTree left;
private BinaryTree right;
private int height = 1;

public BinaryTree()
{
    left = null;
    right = null;
}

public BinaryTree(int theInfo)
{
    Scanner sc = new Scanner(System.in);
    int intNum;
    String s;

    info = theInfo;

    System.out.print("Does the node " + info + " have a left child (y or n)? ");
    s = sc.next();
    if (s.equals("y"))
    {
        System.out.print ("What value should go in the left child node? ");
        intNum = sc.nextInt();
        left = new BinaryTree(intNum);
    }
    System.out.print("Does the node " + info + " have a right child (y or n)? ");
    s = sc.next();
    if (s.equals("y"))
    {
        System.out.print ("What value should go in the right child node? ");
        intNum = sc.nextInt();
        right = new BinaryTree(intNum);
    }
}

int heightLeft = 0;
int heightRight = 0;


public int getHeight()
{
    int counterOld = 0;
    int counter = 0;
     if (left != null)
    {
        counter++;

        if (counter > counterOld)
        {   
            counterOld = counter;
        }
        counter += left.getHeight();
    }
    if (left == null)
    {    System.out.println("counter is: " + counter + " and counterOld is: " + counterOld);
        /*if (counter > counterOld)
        {   
            counterOld = counter;
        } */
        counter = 0;

    }
    if (right != null)
    {  
        counter++;
        if (counter > counterOld)
        {
          counterOld = counter;
        }

        counter += right.getHeight();
    }
    if (right == null)
    {  System.out.println("counter is" + counter + " and counterOld is: " + counterOld);
        /*if (counter > counterOld)
        {
          counterOld = counter;
        } */
      counter = 0;

    }
    return counterOld;
 }
}

---

import java.util.Scanner;

public class BinaryTester {

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub

    BinaryTree myTree;
    Scanner sc = new Scanner(System.in);
    int intNum;

    System.out.print("What value should go in the root? ");
    intNum = sc.nextInt();
    myTree = new BinaryTree(intNum);
    System.out.println("Height is " + myTree.getHeight());
}
}

---

    400
    /
   300
   /
  200
  /
100

我用树高函数计数器得到了混合结果。我想根据最低节点计算树倒下的程度。例如上面的树应该是 3 的高度，根被计数为 0。我得到高度 1 的错误结果。如果我输入这样的树，我会得到正确的结果:

      400
    /    \
   300    10
   /     /   \
 100    4    5
        /
       3

这棵树的高度为 3，这正是我要找的。任何人都知道如何调整我的代码以考虑所有树木？

Answer 1

处理树时，递归要容易得多。

public int getHeight(BinaryTree node){
    if(node == null){
        return 0;
    }

    int left = getHeight(node.left);
    int right = getHeight(node.right);

    return Math.max(left, right) + 1;
}

此方法给出以一为基础的高度。如果您想从零开始计数，那么您可以从中减去一个，例如

getHeight(tree) - 1