'''这是二叉树的定义'''
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
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