В порядке обхода BST в python? - PullRequest
Новая
       63

В порядке обхода BST в python?

0 голосов
/ 13 февраля 2020

Существует вопрос о LeetCode, включающий суммирование всех значений узлов дерева, попадающих между указанными левым и правым параметрами. В верхнем решении python использовался следующий код 


class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None 

class Solution(object):
    def rangeSumBST(self, root, L, R):
        """
        :type root: TreeNode
        :type L: int
        :type R: int
        :rtype: int
        """
        return self.inorder(root, 0, L, R)

    def inorder(self, root, value, L, R):
        if root:
            print(root.val) # I added this to say what came of it. 
            value = self.inorder(root.left, value, L, R)
            if root.val >= L and root.val <= R:
                value += root.val
            value = self.inorder(root.right, value, L, R)

        return value

Контрольный пример выглядит следующим образом: 

       10
      /  \
     5    15
    / \    \
   3   7   18

Порядок посещения узлов следующий: 10,5,3,7,15,18 и оператор print подтвердил это.

Возвращенная сумма составила 32, потому что она включала элементы 10,7,15.

Где я запутался - в этом коде я не вижу переменную root обновляется где-нибудь в коде, но, похоже, делает это. Я понимаю, что он использует упорядоченный обход, но я потерял понимание того, как этот код вызывает этот эффект.

Источник: https://leetcode.com/problems/range-sum-of-bst/discuss/193235/Python3-or-Easy-to-understand-or-InOrder-Traversal

...