How to get the path from the root of a binary tree to all leaves in Python?

Question

'''这是二叉树的定义'''
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
'''这是路径函数'''
def dfs(node, result, tmp):
    if node == None:
        return 
    tmp.append(node)
    if node.left == None and node.right == None:
        result.append([i.val for i in tmp])
        return
    dfs(node.left, result, tmp)
    dfs(node.right, result, tmp)

This is my code, but all nodes are printed every time. Then DEBUG discovered that every time it recurses to the right subtree, the tmp array will retain the state of the left subtree before traversing it, which is not the state from the root to the right subtree at all.
Is this a scope problem? But I can't find how to solve it, so I'm asking for an answer here, thank you

Answer 1

It’s a matter of scope. There probably aren’t many problems with your algorithm. The main thing is that you need to know that when passing parameters to a function, especially when passing in variable parameters (in your case, it’s a list), you have to keep it in mind. Countless. Your problem here is mainly focused on tmp. The reason why the state of the left subtree is retained is because when you traverse the left subtree, you add the left subtree to tmp, and then you make the next recursive call Put the added list into the list. If there is only a left subtree, there is no problem. If there is a right subtree, there will be a problem. My language expression ability is limited, so I will post the modified code for you to see

import copy


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


def dfs(node, result, tmp=list()):
    if node is None:
        return

    tmp.append(node)
    # 这里需要用拷贝而不是用 = 赋值，也可以遍历赋值
    tmp1 = copy.deepcopy(tmp)

    if node.left is None and node.right is None:
        result.append([i.val for i in tmp])
        return

    if node.left is not None:
        dfs(node.left, result, tmp)
    # 遍历右子树需要带上不同的变量，否则左子树的tmp和右子树的tmp都指向一块内存
    if node.right is not None:
        dfs(node.right, result, tmp1)


if __name__ == '__main__':
    node1 = TreeNode('a')
    node2 = TreeNode('b')
    node3 = TreeNode('c')
    node4 = TreeNode('d')
    node5 = TreeNode('e')
    node6 = TreeNode('f')
    node7 = TreeNode('g')

    node1.left = node2
    node1.right = node3
    node2.left = node4
    node2.right = node5
    node4.left = node6
    node3.left = node7

    r = []
    dfs(node1, result=r)
    print(r)