二叉树最近的叶节点

Submission

运行时间: 34 ms

内存: 17.2 MB

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:
        start = None
        def dfs(root, parent):
            nonlocal start
            if not root:
                return
            if root.val == k:
                start = root
            root.parent = parent
            dfs(root.left, root)
            dfs(root.right, root)
        dfs(root, None)

        queue = deque([start])
        vis = set([start])

        while queue:
            cur = queue.popleft()
            if not cur.left and not cur.right:
                return cur.val
            for nxt in (cur.left, cur.right, cur.parent):
                if nxt not in vis and nxt:
                    queue.append(nxt)
                    vis.add(nxt)
        return -1

Explain

这个题解的思路是先通过 DFS 找到值为 k 的节点作为起点，同时在 DFS 过程中为每个节点记录其父节点。然后从起点开始进行 BFS 搜索，第一个遇到的叶子节点即为离起点最近的叶子节点。在 BFS 的过程中需要记录已访问过的节点避免重复访问。

时间复杂度: O(n)

空间复杂度: O(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:
        start = None
        
        # DFS 找到值为 k 的起点节点，并为每个节点记录父节点
        def dfs(root, parent):
            nonlocal start
            if not root:
                return
            if root.val == k:
                start = root
            root.parent = parent
            dfs(root.left, root)
            dfs(root.right, root)
        
        dfs(root, None)

        queue = deque([start]) # BFS 队列，初始为起点
        vis = set([start]) # 记录已访问节点

        # BFS 搜索最近的叶子节点
        while queue:
            cur = queue.popleft()
            if not cur.left and not cur.right: # 找到叶子节点
                return cur.val
            # 将当前节点的左右子节点和父节点加入队列
            for nxt in (cur.left, cur.right, cur.parent):
                if nxt not in vis and nxt:
                    queue.append(nxt)
                    vis.add(nxt)
        
        return -1

Explore

在执行DFS找到值为k的节点后，记录每个节点的父节点是为了之后的BFS搜索能够从找到的节点向其父节点方向扩展，确保能够探索所有可能的路径以找到最近的叶节点。由于二叉树结构只允许从父节点到子节点的单向访问，没有记录父节点信息将无法从子节点回溯到父节点，限制了搜索的完整性。

BFS（广度优先搜索）按照从近到远的顺序访问节点，即它首先访问距起始点最近的节点。在此算法中，BFS从找到的起点k开始，依次检查节点的所有相邻节点（子节点和父节点），并将它们加入队列。第一个在BFS过程中遇到的叶节点自然是从起点到达的最近叶节点，因为BFS保证了最先访问所有更接近的非叶节点。

此算法在DFS过程中将停止于首次发现的值为k的节点，并将其设为起点。因此，如果树中有多个节点的值为k，算法只会处理并从第一个找到的这样的节点开始BFS搜索。这意味着搜索结果可能依赖于节点值k在树中出现的顺序和DFS的遍历顺序。

在BFS中，`nxt not in vis and nxt`检查确保了两件事：首先，`nxt not in vis`确保不会重复访问已经访问过的节点，这是防止无限循环并保证效率的关键；其次，`nxt`检查确保只有存在（非空）的节点被加入到队列中，避免了对空（None）节点的无效操作。这两个检查是为了确保BFS的正确性和效率。