Kotlin递归实现二叉树depth()方法求解二叉树深度

问题背景 #

我正在尝试通过递归方式编写代码求解二叉树的深度，目前已基于Kotlin密封类完成Tree基础结构、isEmpty()、size()方法及空节点的depth()逻辑，但Node类中的depth()递归方法尚未完成，仅尝试调用isEmpty()做判断，现有未完成代码如下：

sealed class Tree <A>{
    abstract fun isEmpty() : Boolean
    abstract fun size() : Int
    abstract fun depth() : Int
}

private data class Node <A >(
    val value : A,
    val left : Tree <A>,
    val right : Tree <A>
) : Tree <A >() {
    override fun isEmpty(): Boolean = false

    override fun size(): Int = 1 + left.size() + right.size()

    override fun depth(): Int {
         if (!left.isEmpty()) // 仅写了判断逻辑，未完成递归实现
    }
}

private object Empty : Tree<Nothing>() {
    override fun isEmpty(): Boolean = true
    override fun size(): Int = 0
    override fun depth(): Int = 0
}

fun <A> emptyTree () : Tree<A> = Empty as Tree<A>
fun <A> treeNode (
    value : A,
    left : Tree<A> = emptyTree() ,
    right : Tree<A> = emptyTree()
): Tree<A> = Node(value, left, right)


fun main(){
    var tree : Tree<Int> = emptyTree()
    tree = treeNode(5,treeNode(3,treeNode(2,treeNode(1)),treeNode(4)),treeNode(8,emptyTree(),treeNode(10)));
    // 测试代码
    println(tree.size())
    println(tree.depth())
}

测试用例为包含7个节点的二叉树，需要补全depth()方法，运行后正确输出该二叉树的深度。

实现方案 #

二叉树深度的递归逻辑非常直接：

• 空节点深度为0（已经在Empty类中实现了该逻辑）
• 非空节点的深度 = 左右子树深度的最大值 + 1（当前节点本身占1层深度）

不需要额外通过isEmpty()做分支判断，因为左右子树无论是Node实例还是Empty实例，都已经实现了depth()方法，直接递归调用即可，补全后的Node.depth()代码如下：

override fun depth(): Int {
    return 1 + maxOf(left.depth(), right.depth())
}

运行结果 #

补全代码后运行main函数，输出结果为：

7
4

其中7是二叉树的节点总数，4是该二叉树的深度（根节点5到最左侧叶子节点1的路径共4层，为整棵树的最大深度），结果符合预期。

内容的提问来源于stack exchange，提问作者funnylookingcode