1198. 找出所有行中最小公共元素 - Kotlin 与运算

Problem: 124. 二叉树中的最大路径和

思路

设searchTree(node:TreeNode?):Int返回的是以当前节点为根节点的子树的最大链表路径和

• 当我们考虑最大路径和时，可以考虑根节点为中间节点，拼接左节点路径和右节点路径
• 当我们考虑最大的链表路径时，根节点就不能再作为中间节点了，如果根节点拼接了左路径和右路径，再被其父节点拼接，则根节点本身延伸出了三条分支，不满足题意
• 对于链表路径而言，我们只能从左节点和右节点的链表路径中选一条，然后拼接上根节点本身，形成一条更长的链表

考虑到我们计算一个节点的路径需要同时考虑左节点和右节点的链表路径，因此应当先从叶子节点开始算起，即后序遍历

最大路径和应当计算该节点的值+左链表路径和（可选）+右链表路径和（可选）

链表路径应当计算该节点的值+左链表路径/右链表路径（也可以二者都不选）

复杂度

• 时间复杂度:
• 空间复杂度:

Code

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    var max=Int.MIN_VALUE
    fun maxPathSum(root: TreeNode?): Int {
        searchTree(root)
        return max
    }

    fun searchTree(root:TreeNode?):Int{
        if(root==null){
            return 0
        }else{
            val leftPath=searchTree(root.left)
            val rightPath=searchTree(root.right)
            
            max=Math.max(max,Math.max(leftPath,0)+Math.max(rightPath,0)+root.`val`)
            
            var path=Math.max(leftPath,rightPath)
            path=Math.max(path,0)
            return path+root.`val`
        }
    }
}