T1

  • 思路：

已知前序遍历： 根-左-右 中序遍历：左-根-右 还原二叉树

首先前序遍历的第一个点一定是当前树的根节点，那么可以根据其值在中序遍历中确定位置 i。这样就将原来树的中序遍历划分为了左子树和右子树的中序遍历。同样可以根据左右子树的长度再去前序遍历中进行左右子树的划分。

  • 扩展：

这题如果是已知中序遍历和后序遍历也可以按照类似方法做。

T2

  • 思路

这题实际上是要我们确定树B 是否是 树A的子树，而不是子节点。

  1. 根据树B的 root 值到树A中去查询找到值相等的点；然后遍历以该点为根节点树的所有值是否和树B中对应点的值相等；
  2. 如果 步骤1 返回 false，那么继续判断树B 是否是 树A的左子树的子树；
  3. 如果 步骤2 返回 false，那么继续判断树B 是否是 树A的右子树的子树；

T3

思路：

题目要求查找栈中的最小元素，而且要求时间复杂度为 O(1)

由于时间复杂度为 O(1)，必须是随机查找。这里可以使用双栈法。

双栈法：生成两个栈，栈2作为辅助栈，每次栈1 插入一个元素 栈2 也进行比较后插入；

https://blog.nowcoder.net/n/ceb3214b89594af481ef9b794c75a929