Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.4k views
in Technique[技术] by (71.8m points)

python - Obtain all root to leaf paths in binary tree while also identifying directions

I have to obtain all the root-to-leaf paths in a binary tree. Now this is usually an easy task, but now I have to identify the left and right nodes as well. That is, when I'm going into a node's left subtree, the node should be recorded in the path as !abc, where abc is node name. When going into the right subtree, the node should be recorded as is. So if my tree is 1(left)2 (right)3, then the two paths that must be saved are !1->2 and 1->3. This is my code:

def get_tree_path(root, paths, treepath):
    if not root:
        return
    if not root.left and not root.right:
        treepath.append(root.data)
        paths.append(treepath)
        
    if root.left:
        treepath.append('!'+root.data[0])
        get_tree_path(root.left, paths, treepath)

    if root.right:
        treepath.append(root.data[0])
        get_tree_path(root.right, paths, treepath)

This does obtain the paths. But the left and right subtree paths are all joined together. That is, for the example given above, I get [!1, 3, 1, 2] as output. I have tried many suggestions given here: print all root to leaf paths in a binary tree and binary search tree path list but I'm only getting more errors. Please help.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

The problem is that when you save your treepath to path you don't delete the contents of treepath.

To do that you need to create a new list for every recursive call:

if root.left:
    treepath_left = list(treepath)
    treepath_left.append('!'+root.data[0])
    get_tree_path(root.left, paths, treepath_left)

if root.right:
    treepath_right = list(treepath)
    treepath_right.append(root.data[0])
    get_tree_path(root.right, paths, treepath_right)

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

2.1m questions

2.1m answers

34 comments

47.0k users

...