leetcode之124二叉树中的最大路径和Golang

标签:最大路   题目   bool   左右子树   必须   sum   lex   思路   str   

题目描述

给定一个非空二叉树,返回其最大路径和。

本题中,路径被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。

示例 1:

输入:[1,2,3]

       1
      /      2   3

输出:6

示例 2:

输入:[-10,9,20,null,null,15,7]

   -10
   /   9  20
    /     15   7

输出:42

算法

在本题中采用了递归的方法,思路就是遍历每一个结点,然后取得最大值,设结点node,它的左子树的最大值为lNode,它的右子树的最大值为rNode,那么对于结点node的最大路径和为:

max(node.Val,node.Val+lNode,node.Val+rNode,node.Val+lNode+rNode,lNode,rNode),就是获取他们中的最大值

但是我们在求结点node的子树的最大值的时候,需要注意一下几个方面

  • 必须包含子树的根结点的值
  • 必须只能包含子树的一边子树,而不能同时包含左右子树

算法步骤如下:

  • 首先定义递归函数的全局变量res=node.Val
  • 然后定义递归函数,参数就是一个结点node
    • 如果res<node.Val,就将node.Val的结果赋值给res
    • 如果node的左子树存在,调用递归函数,传入node.Left,得到结果lNode
      • 如果res<node.Val+lNode,那么res=node.Val+lNode
      • 如果res<lNode,那么res=lNode
    • 如果node的右子树存在,调用递归函数,传入node.Right,得到结果rNode
      • 如果res<node.Val+rNode,那么res=node.Val+rNode
      • 如果res<rNode,那么res=rNode
    • 当左右子树同时存在的时候,还要比较res<node.Val+lNode+rNode
    • 递归函数的返回值为max(node.Val,node.Val+lNode,node.Val+rNode)

代码

func maxPathSum(root *TreeNode) int {
	if root == nil {
		return 0
	}
	res := root.Val
	var findMax func(node *TreeNode) int
	findMax = func(node *TreeNode) int {
		var lExist, rExist bool
		var Lroot, Rroot int
		tmpMax := node.Val
		if res < node.Val {
			res = node.Val
		}
		if node.Left != nil {
			lExist = true
			Lroot = findMax(node.Left)
			if res < node.Val+Lroot {
				res = node.Val + Lroot
			}
			if res < Lroot {
				res = Lroot
			}
			if tmpMax < node.Val+Lroot {
				tmpMax = node.Val + Lroot
			}
		}
		if node.Right != nil {
			rExist = true
			Rroot = findMax(node.Right)
			if res < node.Val+Rroot {
				res = node.Val + Rroot
			}
			if res < Rroot {
				res = Rroot
			}
			if tmpMax < node.Val+Rroot {
				tmpMax = node.Val + Rroot
			}
		}
		if lExist && rExist {
			// 同时存在左子树和右子树
			if res < node.Val+Lroot+Rroot {
				res = node.Val + Lroot + Rroot
			}
		}
		return tmpMax
	}
	_ = findMax(root)
	return res
}

leetcode之124二叉树中的最大路径和Golang

标签:最大路   题目   bool   左右子树   必须   sum   lex   思路   str   

原文地址:https://www.cnblogs.com/gyyyl/p/14166814.html

版权声明:完美者 发表于 2020-12-25 12:51:52。
转载请注明:leetcode之124二叉树中的最大路径和Golang | 完美导航

暂无评论

暂无评论...