标签：最大路   题目   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