LeetCode - 104. Maximum Depth of Binary Tree

問題

04. Maximum Depth of Binary Tree - こんな感じのツリーが与えられて、これの深さ（高さ）を求める

    3
   / \
  9  20
    /  \
   15   7

テストデータ

問題には Given binary tree [3,9,20,null,null,15,7] って配列っぽく書かれているが、実際はこんな TreeNode オブジェクト

#<TreeNode:0x00000000011105e8 @val=3, @left=#<TreeNode:0x00000000011104a8 @val=9, @left=nil, @right=nil>, @right=#<TreeNode:0x0000000001110458 @val=20, @left=#<TreeNode:0x0000000001110408 @val=15, @left=nil, @right=nil>, @right=#<TreeNode:0x00000000011103b8 @val=7, @left=nil, @right=nil>>>

なので、テストデータはこんな感じで作ってみた

Definition for a binary tree node.
  class TreeNode
    attr_accessor :val, :left, :right
    def initialize(val)
      @val = val
      @left, @right = nil, nil
    end
end

# t - top, l - left, r - right
t = TreeNode.new(3)
tl = TreeNode.new(9)
tr = TreeNode.new(20)
trl = TreeNode.new(15)
trr = TreeNode.new(7)

t.left = tl
t.right = tr
  tr.left = trl
  tr.right = trr

p t # => #<TreeNode:0x00000000011105e8 @val=3, @left=#<TreeNode:0x00000000011104a8 @val=9, @left=nil, @right=nil>, @right=#<TreeNode:0x0000000001110458 @val=20, @left=#<TreeNode:0x0000000001110408 @val=15, @left=nil, @right=nil>, @right=#<TreeNode:0x00000000011103b8 @val=7, @left=nil, @right=nil>>>

解答

再帰を使って解くことになる。再帰、もうちょっと慣れないとな...

# 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 max_depth(root)
  if !root.nil?
    ld = max_depth(root.left)
    rd = max_depth(root.right)
    1 + [ld, rd].max
  else
    0
  end
end

• ノードが nil じゃなければ、その次のノード root.left root.right を再帰的によび、左右のノードがエッジかどうかを調べる
• 1 + recursive_func()で呼ばれた回数（ツリーを降りた回数）を数える
• この if !root.nil? は if root でもいけるようだ

if object tests if object isn't either nil or false. !object.nil? tests if object isn't nil. So when object is false, they have different values.

つまりこれでいいのか...

def max_depth(root)
  if root
    1 + [max_depth(root.left), max_depth(root.right)].max
  else
    0
  end
end

スコア

Runtime: 40 ms, faster than 52.11% of Ruby online submissions for Maximum Depth of Binary Tree.
Memory Usage: 9.8 MB, less than 100.00% of Ruby online submissions for Maximum Depth of Binary Tree.