如何从递归函数转换为非递归函数

Question

如何将以下递归代码转换为非递归代码？

特别是，我正在查看最后2行代码。我希望我能得到帮助或线索，因为我目前完全一无所知。

def newNode(data):
    return node(data)
  
# Function to print Leaf Nodes at
# a given level
def PrintLeafNodes(root, level):
    if (root == None):
        return
  
    if (level == 1):
        if (root.left == None and
            root.right == None):
            print(root.data, end = " ")
     
    elif (level > 1):
        PrintLeafNodes(root.left, level - 1) #convert from recursive to non recursive
        PrintLeafNodes(root.right, level - 1) #convert from recursive to non recursive

Answer 1

您可以通过访问此网站来更改和调整代码。我也试着为你调整代码。

def PrintLeafNodes(root): 
      
    # Set current to root of binary tree 
    current = root  
    stack = [] # initialize stack 
    done = 0 
      
    while True: 
          
        # Reach the left most Node of the current Node 
        if current is not None: 
              
            # Place pointer to a tree node on the stack  
            # before traversing the node's left subtree 
            stack.append(current) 
          
            current = current.left  
  
          
        # BackTrack from the empty subtree and visit the Node 
        # at the top of the stack; however, if the stack is  
        # empty you are done 
        elif(stack): 
            current = stack.pop() 
            print(current.data, end=" ") # Python 3 printing 
          
            # We have visited the node and its left  
            # subtree. Now, it's right subtree's turn 
            current = current.right  
  
        else: 
            break
       
    print(current.data, end = " ")