Skip to content

Commit db5565a

Browse files
screnaryscrenary
committed
2020.05.04, tree exercise
1 parent aadd34a commit db5565a

3 files changed

Lines changed: 116 additions & 0 deletions

File tree

‎654_constructMaxBinaryTree.py‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
""" 给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：
2+
二叉树的根是数组中的最大元素。
3+
左子树是通过数组中最大值左边部分构造出的最大二叉树。
4+
右子树是通过数组中最大值右边部分构造出的最大二叉树。
5+
"""
6+
7+
class TreeNode:
8+
def __init__(self, x):
9+
self.val = x
10+
self.left = None
11+
self.right = None
12+
13+
class Solution:
14+
def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
15+
if nums == []: return None
16+
max_num = max(nums)
17+
max_index = nums.index(max_num)
18+
root = TreeNode(max_num)
19+
root.left = self.constructMaximumBinaryTree(nums[0 : max_index])
20+
root.right = self.constructMaximumBinaryTree(nums[max_index + 1 :])
21+
return root

‎tree_124_maxPathSum.py‎

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
""" 给定一个非空二叉树，返回其最大路径和。
2+
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
3+
"""
4+
5+
class TreeNode:
6+
def __init__(self, x):
7+
self.val = x
8+
self.left = None
9+
self.right = None
10+
11+
# import sys
12+
# MAX_INT = sys.maxsize
13+
14+
class Solution:
15+
def maxPathSum_good(self, root):
16+
def max_gain(node):
17+
# post order traverse
18+
nonlocal max_sum
19+
if node is None:
20+
return 0
21+
left_gain = max(max_gain(node.left), 0)
22+
right_gain = max(max_gain(node.right), 0)
23+
24+
# max path with node as the top most node
25+
merge_gain = left_gain + right_gain + node.val
26+
if merge_gain > max_sum:
27+
max_sum = merge_gain
28+
29+
return node.val + max(left_gain, right_gain)
30+
31+
max_sum = float('-inf')
32+
max_gain(root)
33+
return max_sum
34+
35+
# def __init__(self):
36+
# self.maxPath = -MAX_INT
37+
38+
# def maxPathSum(self, root: TreeNode) -> int:
39+
# # too slow
40+
# if root is None: return # do nothing
41+
# tmp = self.getMaxPathPerNode(root)
42+
# if tmp > self.maxPath:
43+
# self.maxPath = tmp # update state
44+
# self.maxPathSum(root.left)
45+
# self.maxPathSum(root.right)
46+
# return self.maxPath
47+
48+
# def getMaxPathPerNode(self, root):
49+
# if root is None:
50+
# return 0
51+
# mp_l = self.dfs(root.left, 0, -MAX_INT)
52+
# mp_r = self.dfs(root.right, 0, -MAX_INT)
53+
# # print(mp_l, mp_r)
54+
# return max(mp_l+root.val, mp_r+root.val, mp_l+mp_r+root.val, root.val)
55+
56+
# def dfs(self, root, tmp, max_p):
57+
# if root is None:
58+
# return max_p
59+
# if tmp + root.val > max_p:
60+
# max_p = tmp+root.val
61+
# max_l = self.dfs(root.left, tmp + root.val, max_p)
62+
# max_r = self.dfs(root.right, tmp + root.val, max_p)
63+
# return max(max_l, max_r)

‎tree_129_sumNumbers.py‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
""" 给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
2+
例如，从根到叶子节点路径 1->2->3 代表数字 123。
3+
计算从根到叶子节点生成的所有数字之和。
4+
"""
5+
6+
class TreeNode:
7+
def __init__(self, x):
8+
self.val = x
9+
self.left = None
10+
self.right = None
11+
12+
class Solution:
13+
def sumNumbers(self, root: TreeNode) -> int:
14+
res = []
15+
def dfs(root, numstr):
16+
if root is None: return
17+
if root.left is None and root.right is None:
18+
res.append(numstr+str(root.val))
19+
return
20+
dfs(root.left, numstr+str(root.val))
21+
dfs(root.right, numstr+str(root.val))
22+
dfs(root, "")
23+
return sum(list(map(int, res)))
24+
25+
def sumNumbers_better(self, root):
26+
def helper(root, pre):
27+
if not root: return 0
28+
pre = pre*10 + root.val
29+
if not root.left and not root.right:
30+
return pre
31+
return helper(root.left, pre) + helper(root.right, pre)
32+
return helper(root, 0)

0 commit comments

Comments
 (0)