331. Verify Preorder Serializati
2020-05-24 本文已影响0人
xxxcoder
key tips
先序遍历，利用stack重建遍历过程
算法1
考虑栈s, 和当前节点x
- 如果x是数字，入栈
- 如果x是'#', 考察栈顶元素y，
- 如果y是数字，则表明x是y的左子树，x入栈，为下一个节点提供提示，表明下一个节点是当前子树的右节点
- 如果y是#，则表示x是当前子树的右节点，从栈中弹出两个元素，并考察当前栈顶元素 y',
- 如果y'是'#'，则表示弹出的子树是下一个子树的右子树，继续出栈
- 如果y'是数字，则表明弹出的子树是下一子树的左子树，压入'#'为下一个元素提供提示，结束出栈操作
