Kotlin 题解 | #牛群的最大高度#

/**
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
object Solution {
    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
        * @param root TreeNode类 
        * @return int整型
    */
    fun findMaxHeight(root: TreeNode?): Int  {
        // write code here
        var maxResult = 0
        // maxResult = preListRecurrence(root, maxResult)
        // maxResult = middleListRecurrence(root, maxResult)
        // maxResult = lastListRecurrence(root, maxResult)
        // maxResult = preListStack(root)
        // maxResult = middleListStack(root)
        maxResult = lastListStack(root)
        return maxResult
    }

    // 前序递归
    fun preListRecurrence(root: TreeNode?, maxResult: Int): Int {
        var maxN = maxResult
        if (root != null) {
            if(root?.`val` > maxN) {
                maxN = root.`val`
            }
            maxN = preListRecurrence(root?.left, maxN)
            maxN = preListRecurrence(root?.right, maxN)
        }
        return maxN
    }

    // 中序递归
    fun middleListRecurrence(root: TreeNode?, maxResult: Int): Int {
        var maxN = maxResult
        if (root != null) {
            maxN = middleListRecurrence(root?.left, maxN)
            if(root?.`val` > maxN) {
                maxN = root.`val`
            }
            maxN = middleListRecurrence(root?.right, maxN)
        }
        return maxN
    }

    // 后序递归
    fun lastListRecurrence(root: TreeNode?, maxResult: Int): Int {
        var maxN = maxResult
        if (root != null) {
            maxN = middleListRecurrence(root?.left, maxN)
            maxN = middleListRecurrence(root?.right, maxN)
            if(root?.`val` > maxN) {
                maxN = root.`val`
            }
        }
        return maxN
    }

    // 前序栈
    fun preListStack(root: TreeNode?): Int {
        var maxN = 0
        var stack = mutableListOf<TreeNode?>()
        stack.add(root)
        maxN = root?.`val` ?: 0
        while (!stack.isEmpty()) {
            var root = stack.lastOrNull()
            stack.remove(root)
            if (root?.right != null) {
                 stack.add(root.right)
                 if( (root?.right?.`val` ?: 0) > maxN){
                    maxN = root?.right?.`val` ?: 0
                 }
             }
            if (root?.left != null) {
                stack.add(root.left)
                 if((root?.left?.`val` ?: 0) > maxN){
                    maxN = root?.left?.`val` ?: 0
                 }
             }
        }
        return maxN
    }

    // 中序栈
    fun middleListStack(root: TreeNode?): Int {
        var maxN = 0
        val stack = mutableListOf<TreeNode?>()
        maxN = root?.`val` ?: 0
        var nodeCu = root
        while (nodeCu != null || !stack.isEmpty()) {
            while (nodeCu != null) {
                stack.add(nodeCu)
                nodeCu = nodeCu.left
            }
            nodeCu = stack.lastOrNull()
            stack.remove(nodeCu)
            if(nodeCu?.`val` != null && nodeCu.`val` > maxN) {
                maxN = nodeCu.`val`
            }
            nodeCu = nodeCu?.right
        }
        return maxN
    }

    // 后序栈
    fun lastListStack(root: TreeNode?): Int {
        var maxN = 0
        val stack = mutableListOf<TreeNode?>()
        maxN = root?.`val` ?: 0
        //中间栈
        val output = mutableListOf<TreeNode?>()
        var nodeCu = root
        while (nodeCu != null || !stack.isEmpty()) {
            if (nodeCu != null) {
                output.add(nodeCu)
                stack.add(nodeCu)
                nodeCu = nodeCu.right
            } else {
                nodeCu = stack.lastOrNull()
                stack.remove(nodeCu)
                nodeCu = nodeCu?.left
            }
        }
        while (!output.isEmpty()) {
            var node = output.lastOrNull()
            output.remove(node)
            if(node?.`val` != null && node.`val` > maxN) {
                maxN = node.`val`
            }
        }
        return maxN
    }
}

二叉树的前中后序递归和栈的两种实现