难度: Medium
Submission
运行时间: 53 ms
内存: 17.4 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 isValidSequence(self, root: Optional[TreeNode], arr: List[int]) -> bool:
if root.val != arr[0]:
return False
def dfs(root, i):
if not root:
return False
if i >= len(arr): # >= not >
return False
if not root.left and not root.right:
if root.val == arr[i] and i == len(arr)-1:
return True
else:
return False
if root.val != arr[i]:
return False
return dfs(root.left, i+ 1) or dfs(root.right, i + 1)
return dfs(root, 0)
Explain
该题解通过递归深度优先搜索（DFS）来验证给定数组 arr 是否表示从根节点到某个叶节点的路径。首先，检查根节点的值是否与数组的第一个元素相匹配。若不匹配，直接返回 False。如果匹配，则递归检查其子节点。在递归过程中，维护一个索引 i 来追踪当前访问到数组 arr 的位置。每深入树的下一层，索引 i 增加 1。若到达叶子节点，检查叶子节点的值是否等于数组中对应的元素且此时索引 i 指向数组的最后一个元素，如果都满足，则说明找到了对应的路径。否则，递归检查左右子节点。最终返回值为左子节点或右子节点递归结果的逻辑或（OR）结果。
时间复杂度: 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 isValidSequence(self, root: Optional[TreeNode], arr: List[int]) -> bool:
if root.val != arr[0]: # 检查根节点值是否与数组第一元素相同
return False
def dfs(root, i):
if not root: # 如果节点为空，则返回 False
return False
if i >= len(arr): # 如果索引超过数组长度，则返回 False
return False
if not root.left and not root.right: # 检查是否到达叶子节点
if root.val == arr[i] and i == len(arr)-1: # 如果到达叶子节点，检查值和索引
return True
else:
return False
if root.val != arr[i]: # 检查当前节点值是否与数组对应元素相同
return False
return dfs(root.left, i+ 1) or dfs(root.right, i + 1) # 递归左右子节点
return dfs(root, 0) # 从根节点开始DFS
Explore
在递归函数`dfs`的开始部分，有一个条件检查`if i >= len(arr)`，用于确认当前的索引`i`是否超过了数组`arr`的长度。如果`i`超过或等于数组长度，函数会立即返回`False`，这样可以防止数组索引越界，避免程序崩溃。这是一种常见的边界条件检查，确保程序的健壮性。
这两个条件确保了当前路径正好对应于数组`arr`。第一个条件`root.val == arr[i]`确认当前叶子节点的值与数组中对应位置的值相匹配。第二个条件`i == len(arr)-1`确保这个叶子节点是在数组的最后一个元素处，即没有更多的数组元素需要匹配。这两个条件同时满足，意味着整个数组被完整地且正确地表达了一条从根到叶的路径。
在这种情况下，如果非叶子节点的值与数组中的对应值匹配，递归函数将继续向下检查该节点的子节点（左子节点和右子节点）。如果任一子节点的路径与数组的后续元素不匹配，则对应的递归调用将返回`False`。如果所有子节点的递归调用都返回`False`，则当前节点的递归也将返回`False`。通过逻辑或（OR）操作，只有当至少一个子路径完全匹配时，当前节点路径才被认为是有效的。
递增索引`i`而不是传递整个子数组是为了效率和空间利用。通过简单地递增索引，我们可以避免数组的拷贝或切片操作，这样可以减少内存使用和增加执行速度。每次递归调用只需传递当前索引，使用原始数组，这种方法既简洁又高效。