[Leetcode]29.二叉树中的最大路径和

2021年11月20日 阅读数:3
这篇文章主要向大家介绍[Leetcode]29.二叉树中的最大路径和,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

题目:路径被定义为一条从树中任意节点出发,沿父节点-子节点链接,达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不必定通过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ,返回其 最大路径和 。

示例 1:

输入:root = [1,2,3]
输出:6
解释:最优路径是 2 -> 1 -> 3 ,路径和为 2 + 1 + 3 = 6

示例 2:

输入:root = [-10,9,20,null,null,15,7]
输出:42
解释:最优路径是 15 -> 20 -> 7 ,路径和为 15 + 20 + 7 = 42

bash

 

思想:code

后序遍历,咱们把问题分红两种状况leetcode

状况一:路径包括当前结点(父节点)it

咱们须要将左右子树的路径信息传回,返回的值是子树中最大的那一边加上父节点的和,注意若是出现负值则舍弃不加入。class

返回一边的缘由是,路径不能走回头路。二叉树

状况二:路径不包括当前结点(父节点)遍历

咱们只须要返回左右子树的最大路径便可。im

func maxPathSum(root *TreeNode) int {
	var max int = 0
	var dfs func(root *TreeNode) int
	dfs = func(root *TreeNode) int {
		if root == nil{
			return 0
		}
		left := dfs(root.Left)
		right := dfs(root.Right)
		curmax := root.Val+left+right  //状况二,咱们先计算子树的路径大小,curmax
		if curmax>max{
			max = curmax  //若是比目前最大的还要大,则取而代之
		}
		var outmax int  //状况一,若是考虑父结点,咱们计算出能给父结点提供最大路径的那一边outmax,不一样时使用两边是为了避免重复路径
		if left>right{
			outmax = root.Val+left
		}else{
			outmax = root.Val+right
		}
		if outmax>0 {
			return outmax  //若是是正值,则返回给父结点,等父结点调用更新max
		}
		return 0  //若是左右子树都提供负值,都舍弃返回父结点一个0值
	}
	dfs(root)
	return max
}

题目来源:https://leetcode-cn.com/problems/binary-tree-maximum-path-sum

img