## #2446586

Solution for ALDS1_7_B: Binary Trees by hiroyuking

Source Code Status Test Cases
Policy: public     Reviewed: 41
00.04 sec    8720 KB    119 lines     2894 bytes    2017-07-18 23:38
```#lines = <<'EOS'
# 4
# 1 0 -1
# 0 2 -1
# 2 3 -1
# 3 -1 -1
#EOS

array = lines.split("\n")

N = array[0].to_i
Node = Struct.new(:parent, :left, :right)

nodes = Array.new(N) { Node.new }

def get_depth(id, nodes)
d = 0
while ! nodes[id].parent.nil? do
id = nodes[id].parent
d += 1
end
d
end

def get_height(id, nodes)
#
# puts "id = #{id}, left = #{nodes[id].left}, right = #{nodes[id].right}"
#
return -1 if nodes[id].nil? or id == -1

left_id  = nodes[id].left.nil? ? -1 : nodes[id].left
right_id = nodes[id].right.nil? ? -1 : nodes[id].right

lefth  = get_height(left_id, nodes)
righth = get_height(right_id, nodes)

height = if lefth > righth
lefth + 1
else
righth + 1
end
height
end

def get_sibling(id, nodes)
if nodes[id].parent.nil?
-1
else
pid = nodes[id].parent
p = nodes[pid]

#puts "p.right => #{p.right.class}, p.left #{p.left.class}"

if p.left.nil? and p.right.nil?
-1
else
if p.right == id
return p.left.nil? ? -1 : p.left
end
if p.left  == id
return p.right.nil? ? -1 : p.right
end
end
end
end

for i in 1...(array.size)
carray = array[i].split(" ")
id    = carray[0].to_i
left  = carray[1].to_i
right = carray[2].to_i

# puts "id #{id}, left #{left}, right #{right}"

# set parents for each children
nodes[left].parent  = id if left  != -1
nodes[right].parent = id if right != -1

# set left/right nodes
nodes[id].left  = left if left != -1
nodes[id].right = right if right != -1
end

for index in 0...nodes.size

node = nodes[index]
parent  = node.parent.nil? ? -1 : node.parent
depth   = get_depth(index, nodes)
sibling = get_sibling(index, nodes)

degree = 0
degree += node.right.nil? ? 0 : 1
degree += node.left.nil?  ? 0 : 1

height  = get_height(index, nodes)

type = if node.parent.nil?
"root"
elsif degree == 0
"leaf"
else
"internal node"
end

puts "node #{index}: parent = #{parent}, sibling = #{sibling}, degree = #{degree}, depth = #{depth}, height = #{height}, #{type}"
end

# node 0: parent = -1, sibling = -1, degree = 2, depth = 0, height = 3, root
# node 1: parent = 0, sibling = 4, degree = 2, depth = 1, height = 1, internal node
# node 2: parent = 1, sibling = 3, degree = 0, depth = 2, height = 0, leaf
# node 3: parent = 1, sibling = 2, degree = 0, depth = 2, height = 0, leaf
# node 4: parent = 0, sibling = 1, degree = 2, depth = 1, height = 2, internal node
# node 5: parent = 4, sibling = 8, degree = 2, depth = 2, height = 1, internal node
# node 6: parent = 5, sibling = 7, degree = 0, depth = 3, height = 0, leaf
# node 7: parent = 5, sibling = 6, degree = 0, depth = 3, height = 0, leaf
# node 8: parent = 4, sibling = 5, degree = 0, depth = 2, height = 0, leaf

```
 Compile Error Logs: You are not authorized to see the message.

Status
 Judge: 8/8 Ruby CPU: 00.04 sec Memory: 8720 KB Length: 2894 B 2017-07-18 23:38 2017-07-18 23:38
Results for testcases
 Case # Verdict CPU Time Memory In Out Case Name Case #1: : Accepted 00.04 sec 8564 KB Case #2: : Accepted 00.03 sec 8568 KB Case #3: : Accepted 00.03 sec 8580 KB Case #4: : Accepted 00.03 sec 8720 KB Case #5: : Accepted 00.03 sec 8612 KB Case #6: : Accepted 00.02 sec 8592 KB Case #7: : Accepted 00.02 sec 8624 KB Case #8: : Accepted 00.02 sec 8640 KB
 < prev | / | next >

 Judge Input #  ( | ) Judge Output #  ( | )