C++刷leetcode(124. 二叉树中的最大路径和)【递归】

糖逗

题目描述：

1. 给定一个非空二叉树，返回其最大路径和。
   
2. 
   
3. 本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
   
4. 
   
5. 示例 1:
   
6. 
   
7. 输入: [1,2,3]
   
8. 
   
9.        1
   
10.       / \
    
11.      2   3
    
12. 
    
13. 输出: 6
    
14. 示例 2:
    
15. 
    
16. 输入: [-10,9,20,null,null,15,7]
    
17. 
    
18.    -10
    
19.    / \
    
20.   9  20
    
21.     /  \
    
22.    15   7
    
23. 
    
24. 输出: 42
    
25. 
    
26. 来源：力扣（LeetCode）
    
27. 链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum
    
28. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. #include<iostream>
   
2. #include <malloc.h>
   
3. #include <vector>
   
4. #include <math.h>
   
5. #include <queue>
   
6. #include<vector>
   
7. using namespace std;
   
8. 
   
9. struct TreeNode{
   
10.         int val;
    
11.         TreeNode* left;
    
12.         TreeNode* right;
    
13.         TreeNode(int x): val(x), left(NULL), right(NULL){
    
14.         }
    
15. };
    
16. 
    
17. TreeNode* CreateTree(vector<int> input){
    
18.     TreeNode* res = (TreeNode*)malloc(sizeof(TreeNode)*input.size());
    
19.     for(int i = 0; i < input.size(); i++){
    
20.             res[i].val = input[i];
    
21.             res[i].left = NULL;
    
22.             res[i].right = NULL;
    
23.     }
    
24.     for(int i= 0; i < input.size(); i++){
    
25.             if(2*i+1 < input.size()){
    
26.                     res[i].left = &res[2*i+1];
    
27.             }
    
28.             if(2*i+2 < input.size()){
    
29.                     res[i].right = &res[2*i+2];
    
30.             }
    
31.            
    
32.     }
    
33.     return res;
    
34.         
    
35. }
    
36. 
    
37. void middle(TreeNode* root, vector<vector<int> >& res, int left, int right, int depth){
    
38.     if(root == NULL) return;
    
39.     int insert = left + (right - left) / 2;
    
40.     res[depth][insert] = root->val;
    
41.            
    
42.     middle(root->left, res, left, insert - 1, depth + 1);
    
43.     middle(root->right, res, insert + 1, right, depth + 1);
    
44.     }
    
45. 
    
46. int treeDepth(TreeNode* root){
    
47.     if(root == NULL || root -> val == 0) return 0;
    
48.     return max(treeDepth(root->left) + 1, treeDepth(root->right) + 1);
    
49. }
    
50.       
    
51. void PrintTree(TreeNode* root) {
    
52.     int depth = treeDepth(root);
    
53.     int width = pow(2, depth) - 1;
    
54.     vector<vector<int> > res(depth, vector<int>(width, 0));
    
55.     middle(root, res, 0, width - 1, 0);
    
56.     for(int i = 0; i < res.size(); i++){
    
57.         for(int j = 0; j < res[i].size();j++){
    
58.                 if(res[i][j] == 0){
    
59.                         cout  << " ";
    
60.                 }
    
61.                 else{
    
62.                         cout << res[i][j];
    
63.                 }
    
64.                
    
65.         }
    
66.         cout << endl;
    
67.     }
    
68.     cout << "------------------" << endl;
    
69. }
    
70. 
    
71. int dfs(TreeNode* root, int& res){
    
72.         if(root == NULL) return 0;
    
73.         int left = max(dfs(root -> left, res), 0);
    
74.         int right = max(dfs(root -> right, res), 0);
    
75.         int temp = root -> val + right + left;
    
76.         res = max(res, temp);
    
77.         return root -> val + max(left, right);
    
78.        
    
79. }
    
80. 
    
81. 
    
82. int solution(TreeNode* root){
    
83.         int res = INT_MIN;
    
84.         dfs(root, res);
    
85.         return res;
    
86. }
    
87. 
    
88. int main(void){
    
89.         vector<int> input1;
    
90.     cout << "send numbers for the  tree" << endl;
    
91.     int number1;
    
92.     while(cin >> number1){
    
93.             input1.push_back(number1);
    
94.     }
    
95.     cin.clear();
    
96.     TreeNode* root = CreateTree(input1);
    
97.     PrintTree(root);
    
98.    
    
99.    
    
100.     int res = solution(root);
     
101.     cout << res << endl;
     
102.     return 0;
     
103. }
     
104. 
     

复制代码

注意事项：
1.参考链接：https://leetcode-cn.com/problems ... jing-he-by-ikaruga/

糖逗

1. class Solution {
   
2. public:
   
3.     int comput(TreeNode*root, int &res){
   
4.         if(root == NULL)return 0;
   
5.         int left = comput(root -> left, res);
   
6.         int right = comput(root -> right, res);
   
7.         int both = root -> val + max(left, 0) + max(right, 0);//双侧情况
   
8.         res = max(res, both);
   
9.         return root->val + max(max(left, 0), max(right, 0));//单侧情况
   
10.     }
    
11.     int maxPathSum(TreeNode* root) {
    
12.         if(root == NULL)return 0;
    
13.         int res = INT_MIN;//存在负数的情况
    
14.         comput(root, res);
    
15.         return res;
    
16.     }
    
17. };

复制代码