树的最大值
时间: 2023-11-13 11:07:12 浏览: 21
如果你想要求一棵树的最大值,需要先定义“树”的最大值是什么。是树中节点值的最大值,还是树中路径上节点值的最大值?
如果是第一种情况,可以使用深度优先搜索(DFS)遍历整颗树,记录下已经遍历过的节点值的最大值。递归时比较当前节点值和已经记录的最大值,取较大值更新最大值。
如果是第二种情况,可以使用树的后序遍历(即 DFS 中的 postorder traversal)来求解。在遍历到每个节点时,记录下从该节点出发向下延伸的路径的最大值。递归时比较当前节点值和从其子节点出发的路径最大值,取较大值更新路径最大值。最终遍历完整棵树后,所记录的路径最大值即为答案。
具体实现可以参考下面的代码(假设节点值存储在 TreeNode 类型的 val 属性中):
```
// 记录树节点值的最大值
int maxVal = Integer.MIN_VALUE;
// DFS 遍历树
public void dfs(TreeNode node) {
if (node == null) return;
// 更新节点值的最大值
maxVal = Math.max(maxVal, node.val);
dfs(node.left);
dfs(node.right);
}
// 记录树路径上节点值的最大值
int maxPath = Integer.MIN_VALUE;
// 后序遍历求解
public int maxPathSum(TreeNode root) {
if (root == null) return 0;
int leftMax = Math.max(maxPathSum(root.left), 0);
int rightMax = Math.max(maxPathSum(root.right), 0);
// 更新路径最大值
maxPath = Math.max(maxPath, root.val + leftMax + rightMax);
// 返回从该节点出发向下延伸的路径的最大值
return root.val + Math.max(leftMax, rightMax);
}
```