查找二叉树最大子树和

问题

给定一个二叉树，其每个节点都是整数，或正或负，求所有子树中最大的子树和。

解法

求所有子树中最大的子树和，需要遍历到所有子树，算出所有的和，选出一个最大的和。遍历思路其实就是后序遍历，从下往上，一边遍历一边比较。

// 求出最大数
func max(data1 int, data2 ...int) int {
	max := data1
	for _, d := range data2 {
		if d > max {
			max = d
		}
	}
	return max
}

// 计算 root 节点下所有节点的和
func getChildTreeSum(root *BTNode) int {
	if root == nil {
		return 0
	}
	// 左子树中的和
	leftData := getChildTreeSum(root.Left)
	// 右子树中的和
	rightData := getChildTreeSum(root.Right)
	return leftData + rightData + root.Data
}

// 获取最大子树和
func getMaxChild(root *BTNode) int {
	if root == nil {
		return math.MinInt
	}
	// 计算出当前节点下子树的和
	treeSum := getChildTreeSum(root)
	// 计算左子树上最大的子树和
	leftSum := getMaxChild(root.Left)
	// 计算右子树上最大的子树和
	rightSum := getMaxChild(root.Right)
	// 比较得到最大值
	return max(treeSum, leftSum, rightSum)
}

func main() {
	root := NewBTree(-18)
	root.Left = &BTNode{
		Data: 5,
		Left: &BTNode{
			Data:  -1,
			Left:  &BTNode{Data: 8},
			Right: &BTNode{Data: 9},
		},
		Right: &BTNode{
			Data:  10,
			Left:  &BTNode{Data: -3},
			Right: &BTNode{Data: -5},
		},
	}
	root.Right = &BTNode{
		Data:  7,
		Left:  &BTNode{Data: 6},
		Right: &BTNode{Data: 2},
	}

	maxSum := getMaxChild(root)
	fmt.Println("最大子树和：", maxSum)
}

输出：

最大子树和： 23

如果还要找出最大子树和的父节点呢？只需要稍微改动下就好了：

// 计算 root 节点下所有节点的和
func getChildTreeSum(root *BTNode) int {
	if root == nil {
		return 0
	}
	// 左子树中的和
	leftData := getChildTreeSum(root.Left)
	// 右子树中的和
	rightData := getChildTreeSum(root.Right)
	return leftData + rightData + root.Data
}

// 获取最大子树和
func getMaxChild(root *BTNode) (int, *BTNode) {
	if root == nil {
		return math.MinInt, nil
	}
	// 计算出当前节点下子树的和
	treeSum := getChildTreeSum(root)
	// 计算左子树上最大的子树和
	leftSum, lMaxNode := getMaxChild(root.Left)
	// 计算右子树上最大的子树和
	rightSum, rMaxNode := getMaxChild(root.Right)

	maxSum := treeSum
	maxNode := root
	if leftSum > maxSum {
		maxSum = leftSum
		maxNode = lMaxNode
	}
	if rightSum > maxSum {
		maxSum = rightSum
		maxNode = rMaxNode
	}
	// 比较得到最大值
	return maxSum, maxNode
}

func main() {
	root := NewBTree(-18)
	root.Left = &BTNode{
		Data: 5,
		Left: &BTNode{
			Data:  -1,
			Left:  &BTNode{Data: 8},
			Right: &BTNode{Data: 9},
		},
		Right: &BTNode{
			Data:  10,
			Left:  &BTNode{Data: -3},
			Right: &BTNode{Data: -5},
		},
	}
	root.Right = &BTNode{
		Data:  7,
		Left:  &BTNode{Data: 6},
		Right: &BTNode{Data: 2},
	}

	maxSum, maxNode := getMaxChild(root)
	fmt.Println("最大子树和：", maxSum)
	fmt.Println("最大子树根节点：", maxNode.Data)
}

输出：

最大子树和： 23
最大子树根节点： 5