Pythonにおけるnonlocalの挙動について
質問
preorder traversalとinorder traversalをつかって。木の復元をしたいと思っています。ぐぐったら後述のページが出てきました。Solutionに書かれたソースコードを見てみるとnonlocalがないのにnonlocalであるかのような挙動を意図している部分があります。この挙動について解説してほしいです。
木の復元のアルゴリズムについては理解できているので特に解説の必要はございません。
(参考)LeetCodeの問題解説ページ
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/
具体的には、下記のhelper関数内でpre_idxはnon_localをつかって宣言している。
これは特に違和感はないです。しかしながら、idx_mapはnonlocalで宣言していないのに、index= idx_map[root_val
などと参照することができています。idx_mapもnonlocalを使わないと参照できなさそうなのに特にエラーになることがないのはどうしでなのでしょうか?
LeetCodeのソースコードを引用
class Solution:
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
def helper(in_left = 0, in_right = len(inorder)):
nonlocal pre_idx
# if there is no elements to construct subtrees
if in_left == in_right:
return None
# pick up pre_idx element as a root
root_val = preorder[pre_idx]
root = TreeNode(root_val)
# root splits inorder list
# into left and right subtrees
index = idx_map[root_val]
# recursion
pre_idx += 1
# build left subtree
root.left = helper(in_left, index)
# build right subtree
root.right = helper(index + 1, in_right)
return root
# start from first preorder element
pre_idx = 0
# build a hashmap value -> its index
idx_map = {val:idx for idx, val in enumerate(inorder)}
return helper()