👏

LeetCode 1372. Longest ZigZag Path in a Binary Tree - クロージャからの変数参照

2025/09/07に公開

LeetCode

tech

1372. Longest ZigZag Path in a Binary Tree

Approach

ruby

def longest_zig_zag(root)
    @path_length = 0
    dfs(root, :left, 0)
    return @path_length
end

def dfs(node, go_direction, steps)
  if node
    @path_length = [@path_length, steps].max
    if go_direction == :left
       dfs(node.left, :right, steps + 1)
       dfs(node.right, :left, 1) # go_direction left から node.rightへのアクセスはzigzagでないためステップ数をリセット
    else
       dfs(node.left, :right, 1) # go_direction right から node.leftへのアクセスはzigzagでないためステップ数をリセット
       dfs(node.right, :left, steps+1)
    end
  end
end

rubyでは、数値のようなプリミティブ型は値渡しされる。再帰関数に引数として渡しても更新はできないため、インスタンス変数を利用する。

def change_value(num)
  num = 100
  puts "メソッド内でのnumの値: #{num}"
end

original_num = 10
puts "メソッド呼び出し前のoriginal_numの値: #{original_num}"

change_value(original_num)
puts "メソッド呼び出し後のoriginal_numの値: #{original_num}"

=>
メソッド呼び出し前のoriginal_numの値: 10
メソッド内でのnumの値: 100
メソッド呼び出し後のoriginal_numの値: 10

インスタンス変数を利用しないようにするは、クロージャを利用してローカル変数にアクセスする。

def longest_zig_zag(root)
    path_length = 0
    dfs = -> (node, go_direction, steps) {
      if node
        path_length = [path_length, steps].max
        if go_direction == :left
          dfs.call(node.left, :right, steps + 1)
          dfs.call(node.right, :left, 1)
        else
          dfs.call(node.left, :right, 1)
          dfs.call(node.right, :left, steps+1)
        end
      end
    }

    dfs.call(root, :left, 0)
    
    path_length
end

python

インスタンス変数を利用して、クロージャからpath_lengthの更新を行う。
- クロージャは、外部スコープの変数を読み取ることはできるが、変更するにはnonlocalキーワードを使って明示的な宣言が必要。
- もしクラス内でクロージャを使うなら、selfを通じてインスタンス変数を変更する。

class Solution:
    def longestZigZag(self, root: Optional[TreeNode]) -> int:
      path_length = 0 # インスタンス変数path_legnthを定義
      def dfs(node, go_direction, steps):
        nonlocal path_length
        if node:
          path_length = max(path_length, steps)
          if go_direction == 'left':
            dfs(node.left, 'right', steps+1)
            dfs(node.right, 'left', 1)
          else:
            dfs(node.left, 'right', 1)
            dfs(node.right, 'left', steps+1)
        
      dfs(root, 'left', 0)
      return path_length

typescript

function longestZigZag(root: TreeNode | null): number {
    let path_length :number =  0

    function dfs(node: TreeNode | null, go_direction: string, steps: number){
      if (node){
        path_length = Math.max(path_length, steps)
        if (go_direction =='left'){
          dfs(node.left, 'right', steps+1)
          dfs(node.right, 'left', 1)
        } else {
          dfs(node.left, 'right', 1)
          dfs(node.right, 'left', steps+1)
        }
      }
    }

    dfs(root, 'left', 0)
    return path_length
};

golang

func longestZigZag(root *TreeNode) int {
    var pathLength int

  	var dfs func(node *TreeNode, goDirection string, steps int)
    dfs = func (node *TreeNode, goDirection string, steps int){
      if node != nil {
        pathLength = max(pathLength, steps)
        if goDirection == "left"{
          dfs(node.Left, "right", steps+1)
          dfs(node.Right, "left", 1)
        }else{
          dfs(node.Left, "right", 1)
          dfs(node.Right, "left", steps+1)
        }
      }
    }
    dfs(root, "left", 0)
    return pathLength
}

Go言語ではシングルクォート（'）とダブルクォート（"）を区別する
- シングルクォート ('): rune リテラル
- ダブルクォート ("): string リテラル

学習のポイント

クロージャからのローカル変数の変更方法

言語	クロージャの作成方法	ローカル変数の変更
Ruby	Proc, lambda, ブロック	自動的に変更可能
Python	ネストされた関数	nonlocalが必要
TypeScript	ネストされた関数	自動的に変更可能
Go	関数リテラル	自動的に変更可能

Go言語ではシングルクォート（'）とダブルクォート（"）を区別する

1372. Longest ZigZag Path in a Binary Tree

Approach

学習のポイント

Discussion