56686


## 質問

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のソースコードを引用

[code]

    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()
    
[/code]


CC BY-SA 4.0
2019-07-16T11:03:38.250
56685
2019-07-16T11:31:52.640
32428
question
python python3 アルゴリズム
Pythonにおけるnonlocalの挙動について


値を書き換える場合にnonlocalが必要なのであって、参照だけなら不要らしいですよ。

[【Python3】nonlocalを使って、ある名前空間の外の変数にアクセスする](https://pycarnival.com/nonlocal/)

> ある名前空間の外の変数に代入したい時に使います。

[Python Tips：Python 3 の nonlocal
を使いたい](https://www.lifewithpython.com/2016/06/python-3-nonlocal.html)

> ただし、関数の内側から外側の変数へのアクセスは基本的に「参照」のみが可能です。値を更新するには nonlocal 宣言をしなくてはなりません。

[Pythonのglobalとnonlocal宣言](http://pikesaku.hatenablog.com/entry/2017/02/12/001753)

> 関数内に関数を定義する場合、内側の関数から外側の関数内の変数を変更するために利用  
>  考え方は、global変数と同じ。

[Pythonにおける名前空間とスコープを理解する上でのポイントを押さえよう
(4/4)](https://www.atmarkit.co.jp/ait/articles/1612/09/news030_4.html)

>
> 内側の関数ではローカルスコープの外部にある名前を参照はできるが、その値を変更することはできない（上のglobalキーワードの例では、代入しようとすると同じ名前が新たにローカルスコープに導入されていた。今回は導入される前に、その値を変更しようとしている）。そのため、「n
> +=
> 1」行は「未定義の変数の値を変更しようとした」と解釈されて、実行時に「UnboundLocalError」例外が発生している。こうした状況を避けるためにnonlocalキーワードが利用できる。上のコードを修正すると次のようになる。


CC BY-SA 4.0
2019-07-16T11:31:52.640
56686
2019-07-16T11:31:52.640
26370
56685
answer