FilesExpand file tree

 main

/

0124-binary-tree-maximum-path-sum.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

42 lines (36 loc) · 1.1 KB

 main

/

0124-binary-tree-maximum-path-sum.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

42 lines (36 loc) · 1.1 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

/*

Given root of binary tree, return max path sum (seq of adj node values added together)

Path can only have <= 1 split point, assume curPath has it, so return can't split again

Time: O(n)

Space: O(n)

*/

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode() : val(0), left(nullptr), right(nullptr) {}

* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

* };

*/

class Solution {

public:

int maxPathSum(TreeNode* root) {

int maxPath = INT_MIN;

dfs(root, maxPath);

return maxPath;

}

private:

int dfs(TreeNode* root, int& maxPath) {

if (root == NULL) {

return 0;

}

int left = max(dfs(root->left, maxPath), 0);

int right = max(dfs(root->right, maxPath), 0);

int curPath = root->val + left + right;

maxPath = max(maxPath, curPath);

return root->val + max(left, right);

}

};