Remove distracting text, extract the programming question, provide simple, common, and optimized Java solution for it.

Problem List
0
Debugging...
Run
Submit
00:00:00
Description
Editorial
Editorial
Solutions
Solutions
Submissions
Submissions
Code
Note
Note
Testcase
Testcase
Test Result
124. Binary Tree Maximum Path Sum
Hard
Topics
Companies

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node's values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

 

Example 1:

Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.


Example 2:

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.


 

Constraints:

The number of nodes in the tree is in the range [1, 3 * 104].
-1000 <= Node.val <= 1000
Seen this question in a real interview before?
1/5
Yes
No
Accepted
1.4M
Submissions
3.4M
Acceptance Rate
40.5%
Topics
Dynamic Programming
Tree
Depth-First Search
Binary Tree
Companies
0 - 3 months
DoorDash
24
Google
6
Meta
6
Amazon
6
TikTok
3
Oracle
2
0 - 6 months
Microsoft
6
Wix
2
Baidu
2
6 months ago
Citadel
30
Apple
13
Adobe
9
Flipkart
7
Yandex
6
Bloomberg
4
Uber
4
Salesforce
4
Yahoo
4
Nvidia
3
Similar Questions
Path Sum
Easy
Sum Root to Leaf Numbers
Medium
Path Sum IV
Medium
Longest Univalue Path
Medium
Time Needed to Inform All Employees
Medium
Difference Between Maximum and Minimum Price Sum
Hard
Discussion (183)
Choose a type
Preview
Comment
💡 Discussion Rules

1. Please don't post any solutions in this discussion.

2. The problem discussion is for asking questions about the problem or for sharing tips - anything except for solutions.

3. If you'd like to share your solution for feedback and ideas, please head to the solutions tab and post it there.

Sort by:Best
No comments yet.
1
2
3
4
19
Copyright ©️ 2024 LeetCode All rights reserved
16.9K
183
Java
Auto
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxPathSum(TreeNode root) {
        
    }
}
Restored from local
Ln 1, Col 1
You must run your code first

Repeated DNA Sequences - LeetCode

Problem List
Tag
50. Pow(x, n)

Med.

51. N-Queens

Hard

52. N-Queens II

Hard

53. Maximum Subarray

Med.

54. Spiral Matrix

Med.

55. Jump Game

Med.

56. Merge Intervals

Med.

57. Insert Interval

Med.

58. Length of Last Word

Easy

59. Spiral Matrix II

Med.

60. Permutation Sequence

Hard

61. Rotate List

Med.

62. Unique Paths

Med.

63. Unique Paths II

Med.

64. Minimum Path Sum

Med.

65. Valid Number

Hard

66. Plus One

Easy

67. Add Binary

Easy

68. Text Justification

Hard

69. Sqrt(x)

Easy

70. Climbing Stairs

Easy

71. Simplify Path

Med.

72. Edit Distance

Med.

73. Set Matrix Zeroes

Med.

74. Search a 2D Matrix

Med.

75. Sort Colors

Med.

76. Minimum Window Substring

Hard

77. Combinations

Med.

78. Subsets

Med.

79. Word Search

Med.

80. Remove Duplicates from Sorted Array II

Med.

81. Search in Rotated Sorted Array II

Med.

82. Remove Duplicates from Sorted List II

Med.

83. Remove Duplicates from Sorted List

Easy

84. Largest Rectangle in Histogram

Hard

85. Maximal Rectangle

Hard

86. Partition List

Med.

87. Scramble String

Hard

88. Merge Sorted Array

Easy

89. Gray Code

Med.

90. Subsets II

Med.

91. Decode Ways

Med.

92. Reverse Linked List II

Med.

93. Restore IP Addresses

Med.

94. Binary Tree Inorder Traversal

Easy

95. Unique Binary Search Trees II

Med.

96. Unique Binary Search Trees

Med.

97. Interleaving String

Med.

98. Validate Binary Search Tree

Med.

99. Recover Binary Search Tree

Med.

100. Same Tree

Easy

101. Symmetric Tree

Easy

102. Binary Tree Level Order Traversal

Med.

103. Binary Tree Zigzag Level Order Traversal

Med.

104. Maximum Depth of Binary Tree

Easy

105. Construct Binary Tree from Preorder and Inorder Traversal

Med.

106. Construct Binary Tree from Inorder and Postorder Traversal

Med.

107. Binary Tree Level Order Traversal II

Med.

108. Convert Sorted Array to Binary Search Tree

Easy

109. Convert Sorted List to Binary Search Tree

Med.

110. Balanced Binary Tree

Easy

111. Minimum Depth of Binary Tree

Easy

112. Path Sum

Easy

113. Path Sum II

Med.

114. Flatten Binary Tree to Linked List

Med.

115. Distinct Subsequences

Hard

116. Populating Next Right Pointers in Each Node

Med.

117. Populating Next Right Pointers in Each Node II

Med.

118. Pascal's Triangle

Easy

119. Pascal's Triangle II

Easy

120. Triangle

Med.

121. Best Time to Buy and Sell Stock

Easy

122. Best Time to Buy and Sell Stock II

Med.

123. Best Time to Buy and Sell Stock III

Hard

124. Binary Tree Maximum Path Sum

Hard

125. Valid Palindrome

Easy

126. Word Ladder II

Hard

127. Word Ladder

Hard

128. Longest Consecutive Sequence

Med.

129. Sum Root to Leaf Numbers

Med.

130. Surrounded Regions

Med.

131. Palindrome Partitioning

Med.

132. Palindrome Partitioning II

Hard

133. Clone Graph

Med.

134. Gas Station

Med.

135. Candy

Hard

136. Single Number

Easy

137. Single Number II

Med.

138. Copy List with Random Pointer

Med.

139. Word Break

Med.

140. Word Break II

Hard

141. Linked List Cycle

Easy

142. Linked List Cycle II

Med.

143. Reorder List

Med.

144. Binary Tree Preorder Traversal

Easy

145. Binary Tree Postorder Traversal

Easy

146. LRU Cache

Med.

147. Insertion Sort List

Med.

148. Sort List

Med.

149. Max Points on a Line

Hard

150. Evaluate Reverse Polish Notation

Med.

151. Reverse Words in a String

Med.

152. Maximum Product Subarray

Med.

153. Find Minimum in Rotated Sorted Array

Med.

154. Find Minimum in Rotated Sorted Array II

Hard

155. Min Stack

Med.

156. Binary Tree Upside Down

Med.

157. Read N Characters Given Read4

Easy

158. Read N Characters Given read4 II - Call Multiple Times

Hard

159. Longest Substring with At Most Two Distinct Characters

Med.

160. Intersection of Two Linked Lists

Easy

161. One Edit Distance

Med.

162. Find Peak Element

Med.

163. Missing Ranges

Easy

164. Maximum Gap

Med.

165. Compare Version Numbers

Med.

166. Fraction to Recurring Decimal

Med.

167. Two Sum II - Input Array Is Sorted

Med.

168. Excel Sheet Column Title

Easy

169. Majority Element

Easy

170. Two Sum III - Data structure design

Easy

171. Excel Sheet Column Number

Easy

172. Factorial Trailing Zeroes

Med.

173. Binary Search Tree Iterator

Med.

174. Dungeon Game

Hard

175. Combine Two Tables

Easy

176. Second Highest Salary

Med.

177. Nth Highest Salary

Med.

178. Rank Scores

Med.

179. Largest Number

Med.

180. Consecutive Numbers

Med.

181. Employees Earning More Than Their Managers

Easy

182. Duplicate Emails

Easy

183. Customers Who Never Order

Easy

184. Department Highest Salary

Med.

185. Department Top Three Salaries

Hard

186. Reverse Words in a String II

Med.

187. Repeated DNA Sequences

Med.

188. Best Time to Buy and Sell Stock IV

Hard

189. Rotate Array

Med.

190. Reverse Bits

Easy

191. Number of 1 Bits

Easy

192. Word Frequency

Med.

193. Valid Phone Numbers

Easy

194. Transpose File

Med.

195. Tenth Line

Easy

196. Delete Duplicate Emails

Easy

197. Rising Temperature

Easy

198. House Robber

Med.

199. Binary Tree Right Side View

Med.