代码之家 › 专栏 › 技术社区 › JacobIRR

这里使用的是哪个X阶树遍历(深度优先搜索)?

python-3.x python

JacobIRR · 技术社区 · 6 年前

This leetcode question 使用深度优先遍历快速解决,因为它涉及子集:

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        results = []

        if candidates == None or len(candidates) == 0:
            return results

        candidates = sorted(candidates)

        combination = []
        self.recurse(results, combination, candidates, target, 0)

        return results

    def recurse(self, results, combination, candidates, target, startIndex):
        '''
        walk the tree, looking for a combination of candidates that sum to target
        '''
        print("combination is : " + str(combination))
        if target == 0:
            # must add a copy of the list, not the list itself
            results.append(combination[:])
            return;

        for i in range(startIndex, len(candidates)):
            if candidates[i] > target:
                break

            combination.append(candidates[i])
            self.recurse(results, combination, candidates, target - candidates[i], i)
            combination.remove(combination[len(combination) - 1])

s = Solution()
results = s.combinationSum([2,6,3,7], 7)
print(results)
assert results == [[2, 2, 3], [7]]

…但是,我不能确切地知道这里使用的是哪种类型的遍历。当我看到“nodes”和“left”/“right”属性的用法时,我按顺序遍历:

def inorder(node):
  if node == None: return
  inorder(node.left)
  do_something_with_node(node)
  inorder(node.right)

…但是在这个解决方案中,对节点和左/右子节点的引用并不明确。”节点”是 candidates 在本例中列出,但这是按顺序遍历的吗?还是预订单/后订单?

*更新:我打印了 combination 在顶部 recurse 得到这个:

combination is : []
combination is : [2]
combination is : [2, 2]
combination is : [2, 2, 2]
combination is : [2, 2, 3]
combination is : [2, 3]
combination is : [3]
combination is : [3, 3]
combination is : [6]
combination is : [7]

1 回复 | 直到 6 年前

Primusa 6 年前

这是一个预顺序遍历。这意味着它访问节点的顺序是(根节点、子节点)。这个 recurse 函数本质上是一个美化版本:

def depth_first_search(state):

    if state is solution:
        results.append(state)
    for next_state in next_possible_states:
        if next_state is valid:
            depth_first_search(next_state)

首先,它访问当前节点并检查它是否是解决方案。然后它就转到了孩子们身上。预订单遍历。

推荐文章

July · 如何定义数字间隔,然后四舍五入

1 年前

Community wiki · 对象名称前的单下划线和双下划线的含义是什么?

1 年前