java - 困惑 - 二叉树的高度

标签 java algorithm data-structures tree binary-tree

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

代码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。是否只是每个人的实现问题 - 两种方法都正确吗?

最佳答案

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

根据 Wikipedia :

The height of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree. The depth of a node is the length of the path to its root (i.e., its root path).

The root node has depth zero, leaf nodes have height zero, and a tree with only a single node (hence both a root and leaf) has depth and height zero. Conventionally, an empty tree (tree with no nodes, if such are allowed) has depth and height −1.

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

当然,这些都是定义 - 如果看到与第一个版本一致的定义,我不会太惊讶。

关于java - 困惑 - 二叉树的高度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17449845/

相关文章:

algorithm - 预序和与中序遍历的关系

java - 使用 AndEngine 限制声音播放

algorithm - Newsfeed内容排名算法: graph theory,亲和性与机器学习

algorithm - 有没有Online Judge给用户提供引擎使用的所有测试用例?

swift - 像 Snapchat 一样构建 Firebase 数据库

mysql - SQL查询按时间顺序获取不同表的两列的组合

java - 在 Java 中使用类时遇到很多麻烦

java - 减少内存流量

java - 如何修复 ClassCastExecption 和 NullPointerException?

java - 如何从数据库存储对象?