天池 在线编程 最大子树（自底向上）

文章目录

• • 1. 题目
  • 2. 解题

1. 题目

描述

给你一棵二叉树，找二叉树中的一棵子树，他的所有节点之和最大。
返回这棵子树的根节点。
我会把你返回的节点作为最优子树的树根来打印。
数据保证有且仅有唯一的解。

示例 样例 1: 输入: {1,-5,2,0,3,-4,-5} 输出:3 说明 这棵树如下所示：1/ \-5 2/ \ / \ 0 3 -4 -5 以3为根的子树（只有3一个节点）的和是最大的，所以返回3。样例 2: 输入: {1} 输出:1 说明: 这棵树如下所示：1 这棵树只有整体这一个子树，所以返回1.

https://tianchi.aliyun.com/oj/456013639031220453/490558435244577688

2. 解题

/*** Definition of TreeNode:* class TreeNode {* public:* int val;* TreeNode *left, *right;* TreeNode(int val) {* this->val = val;* this->left = this->right = NULL;* }* }*/class Solution {int ans = INT_MIN;TreeNode *res = NULL; public:/*** @param root: the root of binary tree* @return: the maximum weight node*/TreeNode * findSubtree(TreeNode * root) {// write your code herefind(root);return res;}int find(TreeNode* root){if(!root) return INT_MIN;int l = find(root->left); // 左子树的总和l = (l==INT_MIN ? 0 : l);int r = find(root->right);// 右子树的总和r = (r==INT_MIN ? 0 : r);int s = l+r+root->val; //当前子树的总和if(s > ans)// 记录最大的{ans = s;res = root;}return s;} };

---

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

总结

以上是生活随笔为你收集整理的天池 在线编程 最大子树（自底向上）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。