-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution.rb
More file actions
71 lines (42 loc) · 1.23 KB
/
Solution.rb
File metadata and controls
71 lines (42 loc) · 1.23 KB
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
# Definition for a binary tree node.
class TreeNode
attr_accessor :val, :left, :right
def initialize(val)
@val = val
@left, @right = nil, nil
end
end
# @param {TreeNode} root
# @return {Integer}
def rob(root)
with_root, without_root = traverse root
max_val with_root, without_root
end
def max_val(a, b)
a > b ? a : b
end
def traverse(root)
l_max_with_root = 0; l_max_without_root = 0
r_max_with_root = 0; r_max_without_root = 0
max_with_root = 0; max_without_root = 0
unless root.nil?
l_max_with_root, l_max_without_root = traverse root.left
r_max_with_root, r_max_without_root = traverse root.right
max_with_root = l_max_without_root + r_max_without_root + root.val
max_without_root = max_val(l_max_with_root, l_max_without_root) + max_val(r_max_with_root, r_max_without_root)
end
return max_with_root, max_without_root
end
root1 = TreeNode.new 3
root1.left = TreeNode.new 2
root1.left.right = TreeNode.new 3
root1.right = TreeNode.new 3
root1.right.left = TreeNode.new 1
puts rob root1
root2 = TreeNode.new 3
root2.left = TreeNode.new 4
root2.right = TreeNode.new 5
root2.left.left = TreeNode.new 1
root2.left.right = TreeNode.new 3
root2.right.right = TreeNode.new 1
puts rob root2