时间戳

首页 > 解决方案 > DFS 复杂性，对二叉树中的每个子节点进行两次递归调用

python - DFS 复杂性，对二叉树中的每个子节点进行两次递归调用

问题描述

因此，假设问题是计算二叉树中总和等于某个目标的路径数。

一种简单的方法是为每个子节点递归调用 DFS 两次，一次用于将子节点用于在其之前某处开始的路径，一次用于开始搜索从子节点开始的路径。

这种方法的时间复杂度为 O(4^k)，其中k是树的高度，但是相对于树中的节点数n的复杂度是多少？

我知道常规 DFS 具有 O(n) 时间复杂度，因为它只访问每个树节点一次，但如果我没记错的话，这种方法会访问m 2^m 级的节点。

这是我在python中解决问题的代码。

def cnt_paths(root, target):
    return dfs(root, target, 0, set())


def dfs(node, target, current_sum, visited):
    cnt = 0
    if current_sum + node.val == target:
        cnt += 1

    if node.left:
        cnt += dfs(node.left, target, current_sum + node.val, visited)  # include this node
        if node.left not in visited:
            cnt += dfs(node.left, target, 0, visited)  # start from scratch on next node
            visited.add(node.left)

    if node.right:
        cnt += dfs(node.right, target, current_sum + node.val, visited)
        if node.right not in visited:
            cnt += dfs(node.right, target, 0, visited)
            visited.add(node.right)

    return cnt

标签： pythonalgorithmtreetime-complexitydepth-first-search

解决方案

您列出的复杂性不正确。如果节点的深度为d，则该节点与和的d个不同起点（根、根的子节点、...节点的父节点或节点本身）一起使用。换句话说，表达式针对特定（但具有不同的值）current_sum + node.val被评估d次。nodecurrent_sum

这意味着您总共拥有此类操作的 SUM[depth(node)]。在完美的二叉树中，这个和是：

1 + 2*2 + 3*4 + 4*8 + ... + 2 -1

树的高度在哪里。这个总和小于

∑<sub> =1.. 2 -1

等于（2-1)，即

O(2)

完美二叉树的节点数=2，所以操作数，改写为：

O(log())

推荐阅读