在Python中遍历n遍历树并返回节点实例

Question

最终目标是将节点从一棵树复制到另一棵树。我想访问二叉树中的每个节点并在多次遍历后返回一个节点实例。我似乎无法弄清楚如何返回一个特定的节点。每次返回的节点都匹配根节点的ID时，我将根节点传递给该函数。

class node(): 

    def __init__(self): 
     self.parent = None 
     self.left = None 
     self.right = None 

    def randnode(self, target): 
     global count 
     if target == count: 
      # print 'At target', '.'*25, target 
      return self 
     else: 
      if self.left is not None: 
       count += 1 
       self.left.randnode(target) 
      if self.right is not None: 
       count += 1 
       self.right.randnode(target) 

Answer 1

如果你正在做一个DFS和计数迭代，你甚至不需要递归，只需要一堆地方去尝试，并弹出/推送数据。

def dfs(self,target): 
    count = 0 
    stack = [start] 
    while stack: 
     node = stack.pop() 
     if count == target: 
      return node 

     if node is None: # since we push left/right even if None 
      continue  # stop pushing after we hit None node 
     stack.extend([self.left,self.right]) 
    return -1 # ran out of nodes before count 

加分点：交换栈的队列BFS

---

除此之外，你可能想通过数作为参数，像所有的自我尊重的递归调用，您可以使这个无状态;-)

class node(): 

    def __init__(self): 
     self.parent = None 
     self.left = None 
     self.right = None 

    def randnode(self, target,count=0): 
     if target == count: 
      # print 'At target', '.'*25, target 
      return self 
     if self.left is not None: 
      return self.left.randnode(target,count + 1) 
     if self.right is not None: 
      return self.right.randnode(target,count + 1)