二叉树中给定距离的节点（Amazon SDE-2）

Question

给定一棵二叉树、二叉树中的一个目标节点和一个整数值k，找出距离给定目标节点k距离的所有节点。没有可用的父指针。

link 到 GFG 上的问题：LINK

Example 1:

Input :      
          20
        /    \
      8       22 
    /   \
   4    12 
       /   \
      10    14

Target Node = 8
K = 2

Output: 10 14 22

Explanation: The three nodes at distance 2
from node 8 are 10, 14, 22.

我的代码

from collections import defaultdict
class solver:
    
    def __init__(self):
        self.vertList = defaultdict(list)
        
    def addEdge(self,u,v):
        self.vertList[u].append(v)
        
    def makeGraph(self,root):
        visited = set()
        queue = []
        queue.append(root)
        
        while len(queue) > 0:
            curr = queue.pop(0)
            visited.add(curr)
            
            if curr.left is not None and curr.left not in visited:
                self.vertList[curr.data].append(curr.left.data)
                self.vertList[curr.left.data].append(curr.data)

                queue.append(curr.left)
                
            if curr.right is not None and curr.right not in visited:
                self.vertList[curr.data].append(curr.right.data)
                self.vertList[curr.right.data].append(curr.data)

                queue.append(curr.right)

    def KDistanceNodes(self,root,target,k):
        self.makeGraph(root)
        dist = {}
        for v in self.vertList:
            dist[v] = 0

        visited2 = set()
        queue2 = []
        queue2.append(target)
        
        while len(queue2) > 0:
            curr = queue2.pop(0)
            visited2.add(curr)

            for nbr in self.vertList[curr]:
                if nbr not in visited2:
                    visited2.add(nbr)
                    queue2.append(nbr)
                    dist[nbr] = dist[curr] + 1
        ans = []
        for v in dist:
            if dist[v] == k:
                ans.append(str(v))
            
        return ans

#{ 
#  Driver Code Starts
#Initial Template for Python 3

from collections import deque

# Tree Node
class Node:
    def __init__(self, val):
        self.right = None
        self.data = val
        self.left = None

# Function to Build Tree
def buildTree(s):
    # Corner Case
    if (len(s) == 0 or s[0] == "N"):
        return None

    # Creating list of strings from input
    # string after spliting by space
    ip = list(map(str, s.split()))

    # Create the root of the tree
    root = Node(int(ip[0]))
    size = 0
    q = deque()

    # Push the root to the queue
    q.append(root)
    size = size + 1

    # Starting from the second element
    i = 1
    while (size > 0 and i < len(ip)):
        # Get and remove the front of the queue
        currNode = q[0]
        q.popleft()
        size = size - 1

        # Get the current node's value from the string
        currVal = ip[i]

        # If the left child is not null
        if (currVal != "N"):
            # Create the left child for the current node
            currNode.left = Node(int(currVal))

            # Push it to the queue
            q.append(currNode.left)
            size = size + 1
        # For the right child
        i = i + 1
        if (i >= len(ip)):
            break
        currVal = ip[i]

        # If the right child is not null
        if (currVal != "N"):
            # Create the right child for the current node
            currNode.right = Node(int(currVal))

            # Push it to the queue
            q.append(currNode.right)
            size = size + 1
        i = i + 1
    return root

if __name__ == "__main__":
    x = solver()
    t = int(input())
    for _ in range(t):
        line = input()
        target=int(input())
        k=int(input())

        root = buildTree(line)
        res = x.KDistanceNodes(root,target,k)
        
        for i in res:
            print(i, end=' ')
        print()

输入：

1 N 2 N 3 N 4 5
target = 5
k = 4

它的正确输出是：

而您的代码的输出是：

[]

我的逻辑：

->首先使用BFS/层序遍历将树转化为无向图

->使用BFS遍历图并计算距离

-> Return距离目标k距离的节点

我的看法： 首先，在给定的测试用例中，树表示似乎是按级别顺序排列的，但是，在失败的测试用例中，它看起来不像级别顺序，或者我的逻辑可能是错误的？

输入格式：

自定义输入应该有 3 行。第一行包含一个表示树的字符串，如下所述。第二行包含目标节点的数据值。第三行包含 K 的值。

字符串中的值按照树的level order遍历顺序排列，其中数字表示节点值，字符“N”表示NULL child。

对于上面的树，字符串将是：1 2 3 N N 4 6 N 5 N N 7 N

Answer 1

错误在于“init”中完成的逻辑应该针对每个用例（重新初始化 self.vertList）完成，而不是一开始就完成一次。

变化：

def __init__(self):
    self.vertList = defaultdict(list)

至：

 def __init__(self):
    pass

和：

def KDistanceNodes(self,root,target,k):
    self.makeGraph(root)
    dist = {}
    ...

至：

def KDistanceNodes(self, root, target, k):
    self.vertList = defaultdict(list) # <-- move it here
    self.makeGraph(root)
    dist = {}
    ...

原始代码不断积累节点并“记住”以前的用例。

另外注意你应该 return ans 排序，这意味着你不应该将数字作为字符串附加，这样你就可以要对它们进行排序，请将：ans.append(str(v)) 更改为：ans.append(v) 和 return sorted(ans).

二叉树中给定距离的节点（Amazon SDE-2）

Nodes at given distance in binary tree (Amazon SDE-2)

algorithm

binary-tree

graph

data-structures

python-3.x