难度: Medium
Submission
运行时间: 92 ms
内存: 52.4 MB
### 网友解法：栈
class Solution:
def isPreorder(self, nodes: List[List[int]]) -> bool:
st=[-1]
for i,j in nodes:
while st and st[-1]!=j:
st.pop()
if not st:
return False
st.append(i)
return True
Explain
此题解使用栈的数据结构来验证数组是否表示某二叉树的前序遍历。对于给定的节点数组，每个节点表示为[i, j]，其中i是节点值，j是其父节点值。解法的核心思想是从左到右遍历节点数组，利用栈来维护一个从根节点到当前节点的路径。对于每个节点，如果栈顶元素（即当前父节点）不等于该节点的父节点j，那么就不断弹栈，直到栈顶的元素等于j或者栈为空。如果栈为空，则说明没有找到对应的父节点，返回false。如果找到了，则将当前节点i压入栈中，继续处理下一个节点。遍历结束后，如果没有提前返回false，则说明数组表示的是一种前序遍历。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def isPreorder(self, nodes: List[List[int]]) -> bool:
st = [-1] # 初始化栈，用-1表示栈底元素
for i, j in nodes: # 遍历节点数组
while st and st[-1] != j: # 当栈非空且栈顶元素不是当前节点的父节点时
st.pop() # 弹出栈顶元素
if not st: # 如果栈为空，则说明没有找到合适的父节点
return False # 返回False，表示不是前序遍历
st.append(i) # 将当前节点值压入栈中
return True # 如果正确遍历了所有节点，返回True
Explore
在算法中，-1被压入栈底用来表示一个虚拟的根节点的父节点。这做法主要是为了处理真实根节点（数组中的第一个节点）的情况，即使它没有显式的父节点。当处理到数组的第一个节点时，栈中除了-1没有其他元素，这样可以保证栈非空，使得根节点可以正确入栈。这也确保了在寻找父节点时栈不会为空，避免了额外的空栈检查。
持续弹栈的逻辑基于前序遍历的特性，即一个节点之后紧跟着的是它的子节点。在前序遍历中，如果下一个节点不是当前节点的直接子节点，那么它可能是当前节点的兄弟节点或更远的祖先的其他子节点。因此，如果栈顶元素不是当前节点的父节点，我们需要通过弹栈来回溯到正确的父节点，以正确地反映前序遍历的结构。这确保了每个节点都能正确地与其父节点对应，保持遍历的有效性。
如果在弹栈操作后栈为空，则意味着没有找到当前节点的父节点，这违反了每个节点（除根节点外）都应有一个明确的父节点的前提。返回False是因为这种情况表明给定的数组无法反映一个有效的前序遍历的树结构。是的，这暗示了在有效的前序遍历中，所有的节点（除了根节点）确实有一个共同的祖先，即根节点。
是的，此算法假设每个节点值都是唯一的。这是因为算法使用节点值来确定栈的弹入和弹出操作，如果存在重复的节点值，将无法准确地匹配父节点与子节点的关系。如果节点值可以重复，算法需要调整以便能够处理重复值的情况，可能需要引入额外的标识符（如节点的唯一ID）来保持节点的唯一性，确保父子关系的正确建立。