美文网首页
331. Verify Preorder Serializati

331. Verify Preorder Serializati

作者: xxxcoder | 来源:发表于2020-05-24 12:21 被阅读0次

key tips

先序遍历,利用stack重建遍历过程

算法1

考虑栈s, 和当前节点x

  • 如果x是数字,入栈
  • 如果x是'#', 考察栈顶元素y,
    • 如果y是数字,则表明x是y的左子树,x入栈,为下一个节点提供提示,表明下一个节点是当前子树的右节点
    • 如果y是#,则表示x是当前子树的右节点,从栈中弹出两个元素,并考察当前栈顶元素 y',
      • 如果y'是'#',则表示弹出的子树是下一个子树的右子树,继续出栈
      • 如果y'是数字,则表明弹出的子树是下一子树的左子树,压入'#'为下一个元素提供提示,结束出栈操作

相关文章

网友评论

      本文标题:331. Verify Preorder Serializati

      本文链接:https://www.haomeiwen.com/subject/mtgdahtx.html