Python 解决方案：所有距离为 K 的节点

2024 年 8 月 29 日 | 阅读 6 分钟

在本教程中，我们将解决一个关于二叉树数据结构的题目。题目要求是，如果提供了二叉树的根节点、目标节点和距离值 k，我们需要返回给定二叉树中与目标节点距离为 k 的所有节点的值的列表。

考虑树

                      1
                     / \
                   /     \
                /          \
             2              3
          /    \          /    \
       4         5     6       7
                 / \
                8   9

看上面的树形图

输入: target = 值为 2 的 Node 对象。

root = 指向 1 的 Node 对象。

k = 2。

输出 [8, 9, 3]

如果目标节点是 4，k 等于 4，那么输出

将是 [6, 7]

方法 - 1

这个问题的主要技巧在于，我们必须进行比从上到下的遍历更多的操作。我们需要两种类型的指针。它们是

第一种指针是指向目标节点子节点的指针。例如，如果我们的目标节点是 2 且 k 的值为 2，那么子节点是 4 和 5。
第二种指针是指向目标节点父节点的指针。例如，如果目标节点是 2，这个指针将指向父节点 1。

第一种指针是二叉树结构中常规存在的指针。然而，第二种指针对我们来说是不可用的。因此，我们需要创建这种指针。

一旦我们同时获得这两种指针，我们必须开始从目标节点开始遍历。我们将从目标节点向外辐射状遍历，在每次遍历完成后，我们将 k 减 1。

但是主要问题是如何获取连接到目标节点父节点的节点。我们必须遍历那些不属于目标节点子树的节点。对于上层树中的每个节点，我们将找到该节点到目标节点的距离，设此距离为 dist，然后我们将遍历上层树中节点处的另一个子树，并存储那些与祖先节点距离为 k - dist 的所有节点。

以下是上述方法的代码

代码

# Python program to get the nodes present at the k distance from the target node

# Creating a constructor class for the node
class Node:
 # Defining the method to create a new node
 def __init__(self, val):
  self.val = val
  self.left = None
  self.right = None
   
# Defining the recursive function that will print the nodes k-distanced from the given node
# We will pass the root node to this function, and the distance k
# This will traverse the binary tree in the downward direction
def kDistanceNodeDown(root, k):
   
  # Base Case
  if root is None or k< 0 :
    return
   
  # If we have reached the distance k, print the value of the node
  if k == 0 :
    print (root.val)
    return
   
  # Calling the function recursively for the left and right subtrees of the given root node
  kDistanceNodeDown(root.left, k - 1)
  kDistanceNodeDown(root.right, k - 1)

# Creating a function that will print all the nodes at k-distance from the target node
# The required node can we present in the upward or the downward tree of the target node
# This function will return the distance of the root from the target node, and it will return -1 if the target node is not found in the tree of the given root node.
def kDistanceNode(root, target, k):
   
  # Base Case: If the given tree is empty, return -1
  if root is None:
    return -1

  # If the target node is the same as the root node, we will use the downward traversal function
  # which will print all the nodes present at k distance in the right and left sub-trees of the binary tree with the given root node.
  if root == target:
    kDistanceNodeDown(root, k)
    return 0
   
  # Calling the function recursively to traverse the left subtree
  lt = kDistanceNode(root.left, target, k)
   
  # Checking if the target node is present in the left subtree or not
  if lt != -1:
     
    # If the root node is present at a distance k from the target node,
    # The function will print the root node value
    # lt is the distance from the left child of the root node to the target
    if lt + 1 == k :
      print (root.val)
   
    # Otherwise, we will go to the right subtree and print the nodes present at k - lt - 2 distance
    # We are subtracting 2 because the right child is always 2 edges away from the left child
    else:
      kDistanceNodeDown(root.right, k - lt - 2)

    # Incrementing the distance by 1 and returning the value for parent nodes
    return 1 + lt

  # We will repeat the steps for the right subtree
  # This part will be executed only if we cannot find the target node in the left subtree
  rt = kDistanceNode(root.right, target, k)
  # Checking if the node is present in the right subtree
  if rt != -1:
    # Checking if the root node is present at k distance from the target node
    if (rt + 1 == k):
      print (root.data)
    # Traversing the left subtree
    else:
      kDistanceNodeDown(root.left, k - rt - 2)
    return 1 + rt

  # If the target node was not present in both right and left subtrees, that means the node is not present in the tree
  return -1

# Driver program
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.left.right.left = Node(6)
root.left.right.right = Node(7)
root.left.right.left = Node(8)
root.left.right.right = Node(9)
target = root.left.right
kDistanceNode(root, target, 2)

输出

4
1
2

时间复杂度: 该算法的最坏情况时间复杂度为 O(N)。时间复杂度不超过线性，因为在该算法中没有节点被遍历超过一次。

空间复杂度: 该程序具有 O(h) 的空间复杂度。其中 h 是给定二叉树的高度。

方法 - 2

这种方法比前一种方法更直接。

我们首先遍历整个二叉树，并获取从根节点到目标节点的路径。我们将此路径存储在一个列表中。
在下一步中，我们将遍历列表，对于路径列表中的每个 i 个元素，我们将遍历并打印距离为 (k - i) 的节点。

代码

# Python program to find the nodes at distance k

# Creating a constructor class for the node
class Node:
 # Defining the method to create a new node
 def __init__(self, val):
  self.val = val
  self.left = None
  self.right = None

class Distance:
    node_path = None

    # Defining the main function to perform all the steps
    def distK(self, root, target, K):
        self.node_path = []

        # Finding path of the nodes
        self.Path(root, target)
        res = []
        for i in range(len(self.node_path)):
            self.findKDistance(self.node_path[i], K - i, res, None if i == 0 else self.node_path[i - 1])
        return res
    
    # Defining a function to find the nodes at distance k from the given node
    def findKDistance(self, node, distance, res, cond):

        # Specifying the base condition
        if distance < 0 or node is None or (cond and node == cond):
            return
        if distance == 0:
            res.append(node.val)
        self.findKDistance(node.left, distance - 1, res, cond)
        self.findKDistance(node.right, distance - 1, res, cond)

    # Defining the function that will find the path pf the nodes
    def Path(self, node, t):

        # Specifying the base condition
        if node is None:
            return False

        # Recursively calling the function for the left and right subtrees
        if node == t or self.Path(node.left, t) or self.Path(node.right, t):
            self.node_path.append(node)
            return True
        return False

# Driver program
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.left.right.left = Node(6)
root.left.right.right = Node(7)
root.left.right.left = Node(8)
root.left.right.right = Node(9)
target = root.left.right
d = Distance()
print(d.distK(root, target, 2))

输出

[4, 1]

时间复杂度: O(n)

下一个主题检查二叉树是否为二叉搜索树

← 上一个下一个 →

Python 解决方案：所有距离为 K 的节点

考虑树

方法 - 1

方法 - 2

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Python 问题

Python 解决方案：所有距离为 K 的节点

考虑树

方法 - 1

方法 - 2

相关帖子

正则表达式

Python 中的移动应用程序自动化

Python 中有效的根搜索算法

Python 中的标识符是什么

使用 Tkinter 进行 Python 消息编码-解码

使用 PyQt5 在 Python 中制作简单的注册表单

如何在 Python 中读取文本文件

如何在 Flask 中处理 URL 中的缺失参数

Python 列表中项的平均值

Python 中的 agg() 函数

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器