# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
a = TreeNode(3)
b = TreeNode(2)
c = TreeNode(3)
d = TreeNode(3)
e = TreeNode(1)
a.left = b
a.right = c
b.right = d
c.right = e
f = TreeNode(3)
g = TreeNode(3)
h = TreeNode(3)
# 每一個節點都有兩種情況，那就是偷和不偷，
# 當前節點偷得值為：左節點不偷的值 + 右節點不偷的值 + 當前節點的值
# 當前節點不偷的值為：左節點最大值 + 右節點最大值；注意這里是最大值，是偷和不偷中最大的那個，
class Solution:
def rob(self, root: TreeNode) -> int:
root_list = self.dfs(root)
return max(root_list)
def dfs(self,root):
# 回傳一個串列，第一個代表偷，第二個代表不偷
if not root:
return [0,0]
# 這里left和right都是是一個串列，
left = self.dfs(root.left)
right = self.dfs(root.right)
# 這里當前節點偷得值等于左兒子節點不偷和右兒子節點不偷加上當前節點的值
rob_num = left[1] + right[1] + root.val
# 當前節點不偷，左右節點偷或者不偷的最大值，
not_rob_num = max(left) + max(right)
# 最后同樣回傳一個串列，
return [rob_num,not_rob_num]
A = Solution()
print(A.rob(a))
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/65142.html
標籤：Python
上一篇：Python條件判斷陳述句 if