我想跟踪我写的递归代码

Question

我是递归的新手，我写了代码来查找给定节点的路径，当我干运行我的代码时（跟踪堆栈 ) 它给出了正确的答案但是当我在机器上运行宁相同它没有显示预期的输出有人可以帮助我 找出代码（例如使用调用堆栈）?

    class NewNode:
        def __init__(self, data):
            self.data = data
            self.left = self.right = None
    
    
    arr = [1, 2, 3, 4, 5, 6, 7]
    q = []
    
    
    def create_level_order_binary_tree(i):
        root = None
        if i < len(arr):
            root = NewNode(arr[i])
            root.left = create_level_order_binary_tree(2 * i + 1)
            root.right = create_level_order_binary_tree(2 * i + 2)
        return root
    
    def dfs(root, p, temp_path, path):
        print(temp_path)
        if root is None:
            return path
        if root.data == p:
            if len(temp_path) == 0:
                path.append(root.data)
                return path
            else:
                temp_path.append(root.data)
                path.append(temp_path)
                return path
        temp_path.append(root.data)
        path = dfs(root.left, 6, temp_path, path)
        if len(path) == 0:
            path = dfs(root.right, 6, temp_path, path)
        return path
    
     
 root_node = create_level_order_binary_tree(0)
 path_to_node = dfs(root_node, 6, [], [])
 print(path_to_node`enter code here`)

Answer 1

以下是解决您问题的两种方法。虽然我没有为例程计时，但我怀疑非递归方法会更快，因为它没有那么多地利用堆栈。

首先使用采用简单堆栈（后进先出）数据结构的非递归方法。

from copy import deepcopy
def nrc_dfs(nde, p):
    stck = [(nde, [])]  #LIFO stack implementation
    while stck:
        nd, pth = stck.pop(len(stck)-1)   #pop lastv entry
        if nd:
            pth.append(nd.data)
            if nd.data == p:
                return pth
            stck.append((nd.right, deepcopy(pth)))
            stck.append((nd.left, deepcopy(pth)))
    return []

第二种方法，使用递归技术。

def rc_dfs(nde, p):
    def dfs_sch(nde, p, path):
        if nde:
            path.append(nde.data)
            if nde.data == p:
                return path
            pl = dfs_sch(nde.left, p, [])
            if pl:
                path.extend(pl)
                return path
            pr = dfs_sch(nde.right, p, [])
            if pr:
                path.extend(pr)
                return path
        return []
    return dfs_sch(nde, p, [])

我想跟踪我写的递归代码

I want to trace the recursive code that I have written

python-3.x

recursion

path

tree

tree-traversal