8

我对计算二叉树高度的逻辑有些困惑。

代码 1

public static int findHeight(Tree node) {
    if(node == null)
        return 0;
    else {
        return 1+Math.max(findHeight(node.left), findHeight(node.right));
    }

}

代码 2

public static int findHeight(Tree node) {
    if(node == null)
        return -1;
    else {
        return 1+Math.max(findHeight(node.left), findHeight(node.right));
    }

}

我认为，第二个是正确的，因为它给出了以下代码的正确答案：-

Tree t4 = new Tree(4);
Tree t2 = new Tree(2);
Tree t1 = new Tree(1);
Tree t3 = new Tree(3);
Tree t5 = new Tree(5);

t4.left = t2;
t4.right = t5;

t2.left = t1;
t2.right = t3;

// Prints "Height : 2" for Code 2
// Prints "Height : 3" for Code 1
System.out.println("Height : " + findHeight(t4));

我很困惑，因为许多其他 SO 答案显示了根据代码 1 计算高度的逻辑

矛盾的逻辑

更新：

所有，我对树的高度到底是多少有一个基本的疑问？

1.它是树的根节点和最深节点之间的节点数（包括 - 根节点和最深节点）？

2.是树的根节点和最深节点之间的边数吗？

或者

3.这只是每个人的执行问题 - 两种方法都正确吗？

4

3 回答 3

7

区别在于一棵空树的高度是 -1 还是 0。

根据维基百科：

节点的高度是从该节点到叶子的最长向下路径的长度。根的高度就是树的高度。节点的深度是到其根的路径（即其根路径）的长度。

和

根节点的深度为零，叶节点的高度为零，只有一个节点的树（因此有根和叶）的深度和高度为零。按照惯例，一棵空树（没有节点的树，如果允许的话）的深度和高度为 -1。

所以你可能是对的——第二个同意这一点。

当然，这些都是定义——我不会惊讶于看到与第一个版本一致的定义。

于 2013-07-03T13:56:09.837 回答
0

您的示例高度为 3（t4 是根，t4.left 是 t2，t2.left 是 t1）如果您对高度的理解是（1 个根节点的高度为 1，有一个或两个子节点的根节点的高度为 2 ， ETC）

t4.left = t2;
t4.right = t5;

t2.left = t1;
t2.right = t3;

所以代码1是正确的:))

于 2013-07-03T13:55:32.203 回答
0

代码 0 将根计算为高度 1（根应为 0）。这意味着所有后续的树都将是一棵太多

于 2013-07-03T13:56:40.043 回答