问答题
3.
给定一棵二叉树,它的每个结点都是正整数或负整数,如何找到一棵子树,使得它所有结点的和最大?
【正确答案】
要求一棵二叉树的最大子树和,最容易想到的办法就是针对每棵子树,求出这棵子树中所有结点的和,然后从中找出最大值。恰好二叉树的后序遍历就能做到这一点。在对二叉树进行后序遍历的过程中,如果当前遍历的结点的值与其左右子树和的值相加的结果大于最大值,则更新最大值。如下图所示:
【答案解析】
[考点] 如何求一棵二叉树的最大子树和
提交答案
关闭