Skip to content

step2.md

Latest commit

 

History

History
100 lines (84 loc) · 2.54 KB

step2.md

File metadata and controls

100 lines (84 loc) · 2.54 KB
Raw

step2 他の方の解答を見る

再帰関数から特殊な処理を出す

確かに再帰関数の外側に出した方が意味としてわかりやすい。

下から上げる DFS の修正版

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {TreeNode} root
# @return {Integer}
def min_depth(root)
    min_depth_helper = ->(node){
        return [min_depth_helper.call(node.left), min_depth_helper.call(node.right)].min + 1 if node.left && node.right
        return min_depth_helper.call(node.left) + 1 if node.left
        return min_depth_helper.call(node.right) + 1 if node.right
        1
    }
    return 0 if root.nil?

    min_depth_helper.call(root)
end

上から下に配る DFS の修正版

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {TreeNode} root
# @return {Integer}
def min_depth(root)
    return 0 if root.nil?

    min_depth_helper = -> (node, depth) {
        if node.left && node.right
          return [min_depth_helper.call(node.left, depth + 1), min_depth_helper.call(node.right, depth + 1)].min
        end
        return min_depth_helper.call(node.left, depth + 1) if node.left
        return min_depth_helper.call(node.right, depth + 1) if node.right
        depth
    }

    min_depth_helper.call(root, 1)
end

枝刈り

枝刈りを追加

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {TreeNode} root
# @return {Integer}
def min_depth(root)
    return 0 if root.nil?

    node_and_depth = [[root, 1]]
    result = Float::INFINITY
    while !node_and_depth.empty?
        node, depth = node_and_depth.pop
        result = [result, depth].min if !node.left && !node.right
        next if result <= depth

        node_and_depth << [node.left, depth + 1] if node.left
        node_and_depth << [node.right, depth + 1] if node.right
    end
    result
end

b