文章目錄

• • 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阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的天池 在线编程 最大子树（自底向上）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。