我的递归条件是否适合计算二叉树高度？

我试图在你的帮助下知道我的代码是对还是错，因为遗憾的是我无法检查它。

没有编译错误。 我想要做的是找到二叉树的高度 。 当然，树不必平衡。

二叉树中的每个节点可以有两个节点作为子节点

public int height(RBNode t) { if (t == null) return 0; int heightLeft = height(t.left); int heightRight = height(t.right); if (heightLeft > heightRight) { return heightLeft + 1; } else { return (heightRight + 1); } } 

你认为递归条件是对的吗？ 我的朋友声称它总会返回0。

Answer 1

真正的紧凑版本：

 public int height(RBNode t) { if (t == null) { return 0; } return Math.max(height(t.left), height(t.right)) + 1; } 

Answer 2

看起来很好，虽然我个人改变了最后一点：

 return Math.max(heightLeft, heightRight) + 1; 

我担心你根本无法运行它…为什么你不能围绕这个编写unit testing？ 我对任何无法测试的代码感到紧张:)

Answer 3

乍一看，只要你传入树的头部，它就会返回正确的值。 但是应该很容易构建一个测试来validation这个…

Answer 4

在问题的代码中，我们没有得到高度+1？ 高度定义为从树中根到最深节点的路径长度。 只有一个节点（根）的（带根）树的深度为零。’（维基百科）

如果在问题的代码中，如果将根提供给只有1个节点的树，则将高度设为1，实际上应为0。

如果我错了，请纠正我..