Проблемы с переносом кода с java на python: глобальную переменную считает локальной

Question

Здравствуйте.
Я пришёл из мира Java, и в процессе вынужденного переноса работающего кода (построение дерева из списка его предков) на python столкнулся c проблемой. Код на python возвращает пустое дерево:

parent1 = input().split()
parent =[]
constructed =[]

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
    def __str__(self):
        return str(self.data)


root = TreeNode(0)

def constructNode(i, constructed, parent):

    if constructed[int(i)] is not None:
        return

    if parent[int(i)] == -1:
        constructed[i] = TreeNode(i)
        root = constructed[i] 
        return

    pc = constructed[parent[i]]
    if pc is None:
        constructNode(parent[i], constructed, parent)

    constructed[i] = TreeNode(i)

    if pc is not None:

        if pc.left is None:

            pc.left = constructed[i]
        else:
            pc.right = constructed[i]


def constructTreeBottomUp(parent):
    n = len(parent)
    constructed = [TreeNode(0) for i in range(n)]
    for i in range(n):
        constructNode(i, constructed, parent)
    return root

def getInOrder(root):
    if root is None:
        return
    if root is not None:
        getInOrder(root.left)
        print(root.data + " ")
        getInOrder(root.right)


root1 = constructTreeBottomUp(parent1)
print("T1", root1)//returns T1 = 0

Проблема, видимо, в строке root = constructed[i], где root считается локальной переменной в constructNode(), несморя на определение root = TreeNode() до этого. Я пыталася фиксить global root = TreeNode(),global root = TreeNode(0), но python считает строку либо Py:EQ или вообще "undefined at module level". Не мог бы кто-нибудб, пожалуйста, объяснить, как это в пайтоне фиксится?

Код на Java, для сравнения:

 private class TreeNode
{
    int data;
    TreeNode left;
    TreeNode right;

    TreeNode(int data)
    {
        this.data = data;
    }
}

TreeNode root;

private void constructNode(int i, TreeNode[] constructed, int[] parent)
{
    // node already created for this index 'i'
    if (constructed[i] != null)
    {
        return;
    }
    if (parent[i] == -1)
    {
        constructed[i] = new TreeNode(i);
        root = constructed[i];
        return;
    }
    if (constructed[parent[i]] == null)
    {
        constructNode(parent[i], constructed, parent);
    }

    constructed[i] = new TreeNode(i);

    if (constructed[parent[i]] != null) 
    {
        if (constructed[parent[i]].left == null)
        {
            constructed[parent[i]].left = constructed[i];
        }
        else
        {
            constructed[parent[i]].right = constructed[i];
        }
    }
}

public TreeNode constructTreeBottomUp(int[] parent)
{
    TreeNode[] constructed = new TreeNode[parent.length];

    for (int i = 0; i < constructed.length; i++)
    {
        constructNode(i, constructed, parent);
    }
    return root;
}
public void getInorder(TreeNode root)
    {
        if (root == null) return;
        getInorder(root.left);
        System.out.println(root.data + ", ");
        getInorder(root.right);
    }

Answer 1

В вашем случае не нужны ни глобальные переменные, ни рекурсия. Просто создаем список узлов (причем, сразу с нужными значениями), проходим по списку родителей, привязываем каждый узел к соответствующему родителю.

В класс узла для удобства добавил метод добавления ребенка.

class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

    def add_child(self, node):
        if not self.left:
            self.left = node
        elif not self.right:
            self.right = node
        else:
            raise ValueError('No free children links')

    def __repr__(self):
        return 'TreeNode({self.data!r}, {self.left!r}, {self.right!r})'.format(self=self)


def construct_tree(parents: list):
    # Сразу заполняем список узлами с соответствующими значениями:
    constructed = [TreeNode(i) for i in range(len(parents))]

    root = None  # Корень пока неизвестен
    for i, parent in enumerate(parents):
        # Если индекс родителя -1, значит это корень
        if parent == -1:
            root = constructed[i]
        else:
            # Подвязываем текущий узел соответствующему родителю
            # (отдельная функция construct_node() оказалась не нужна)
            constructed[parent].add_child(constructed[i])

    return root

# Пример использования:
print(construct_tree([-1, 0, 0, 1, 1, 2, 2]))

# Вывод: TreeNode(0, TreeNode(1, TreeNode(3, None, None), TreeNode(4, None, None)), TreeNode(2, TreeNode(5, None, None), TreeNode(6, None, None)))

По поводу различий Python и Java:

1. Строке TreeNode root; примерно соответствует строка root = None, т.е. просто записываем в переменную пустое значение. Вызов TreeNode(0) здесь совершенно не нужен, получается что будет создан лишний объект, который будет перезаписан другим значением, после чего старое значение будет удалено сборщиком мусора. Просто лишняя работа для интерпретатора.
2. Для создания массива с пустыми значениями (TreeNode[] constructed = new TreeNode[parent.length];) можно использовать строку constructed = [None for i in range(len(parent))]. Python - язык с динамической типизацией, тип тут указывать не нужно (да и в общем-то негде), и тем более не нужно заполнять массив при помощи TreeNode(0). В вашей первоначальной реализации получается, что массив уже заранее заполнен узлами, и условие constructed[int(i)] is not None в функции construct_node() будет истинно для любых i.

3. И все-таки о глобальных переменных. Если нужно из функции изменить значение глобальной переменной, то это делается так:

   root = None
   
   def constructNode(i, constructed, parent):
       global root
       ...
       if parent[int(i)] == -1:
           constructed[i] = TreeNode(i)
           root = constructed[i] 
           return
   

4. Ну и последнее, входные данные полностью подготавливать (в данном случае, приводить значения к целым числам) лучше заранее:

   parent1 = [int(item) for item in input().split()]
   

Answer 2

В питоне для присвоения значения глобальной переменной надо в начало фунции добавит global varname, тоесть в вашем случае global root.