LeetCode

Appearance

863. All Nodes Distance K in Binary Tree ​

题目 ​

Given the root of a binary tree, the value of a target node target, and an integer k, return an array of the values of all nodes that have a distance k from the target node.

You can return the answer in any order.

 

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Output: [7,4,1]
Explanation: The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1.

Example 2:

Input: root = [1], target = 1, k = 3
Output: []

 

Constraints:

  • The number of nodes in the tree is in the range [1, 500].
  • 0 <= Node.val <= 500
  • All the values Node.val are unique.
  • target is the value of one of the nodes in the tree.
  • 0 <= k <= 1000
Related Topics
  • 树
  • 深度优先搜索
  • 广度优先搜索
  • 哈希表
  • 二叉树

  • 👍 740
  • 👎 0

    • 思路 ​

    计算出根节点的距离所有节点的绝对位置，找到 target 节点和 root 节点的相对位置，通过相对位置计算结果

    此方案的问题在于，未包含 target 节点的兄弟节点的相对位置，存在遗漏情况

    所以要改变思路，以 target 为中心去计算相对位置

    以 target 为中心去计算位置时， 需要获取 target 的 parent node、right node、 left node 依次遍历到满足目标 k

    TreeNode 类型本身可以获取 right、left node 信息

    问题变成了，如何获取 node 的 parent 信息

    遍历 TreeNode, 通过 hashmap 存取节点以及 parent 信息，将树转化成了图，每一个节点都有路径到达另一个节点

    解法 ​

    py
    # leetcode submit region begin(Prohibit modification and deletion)
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from collections import defaultdict


class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
        parents = {}
        res = []

        def dfs(node: TreeNode, parent):
            if not node:
                return
            parents[node] = parent
            dfs(node.left, node)
            dfs(node.right, node)

        dfs(root, None)

        visited = set()
        queue = []

        queue.append((target, 0))

        while queue:
            node, dist = queue.pop(0)
            if not node or node in visited:
                continue

            visited.add(node)

            if dist == k:
                res.append(node.val)
            elif  dist < k:
                queue.append((node.left, dist + 1))
                queue.append((node.right, dist + 1))
                queue.append((parents[node], dist + 1))

        return res



# leetcode submit region end(Prohibit modification and deletion)

    复杂度分析 ​

    • 时间复杂度 O(N)
    • 空间复杂度 O(N)