在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)