根据二叉树的前序遍历和中序遍历构建二叉树：前序遍历的首元素是根节点，根据中序遍历中根节点的位置计算左子树的节点个数i，则前序遍历[1:1+i]是左子树的前序遍历，中序遍历[:i]是左子树的中序遍历，右子树同理，递归构建可得结果
深度优先遍历，前、中、后序遍历的非递归实现：设栈s，p=root，
前：
while(p||!s.empty()){
while(p){print(p->val);s.push(p);p=p->left;}
if(!s.empty()){p=s.top();s.pop();p=p->right;}
}
中：while(p||!s.empty()){
while(p){s.push(p);p=p->left;}
if(!s.empty()){p=s.top();s.pop();print(p->val);p=p->right;}
}
后序遍历与前、中的实现思路不同，因为若左节点为空，栈中pop出的根节点不能立马被遍历，由根节点得到右节点倒是可以，但没有保存pop出的根节点的数据结果。故需额外声明栈output保存遍历过程，后序遍历：左-右-根，push入output的时候采用根-右-左的顺序，push入output的过程类似前序遍历。while(p||!s.empty()){
while(p){output.push(p->val);s.push(p);p=p->right;}
if(!s.empty()){p=s.top();s.pop();p=p->left;}
}while(!output.empty()){print(output.top());output.pop();}
二叉树的最大宽度，宽度指同一行的最左节点和最右节点连成的线上的节点个数（包含空节点）。广度优先遍历。两个减少节点索引的地方：1.按行索引节点，若是满二叉树，一行的节点按照0，1，。。。索引，索引为i的父节点的左子节点、右子节点索引分别为2i和2i+1，另外层序遍历顺序的节点索引从1开始逐个增1的满二叉树满足父节点p的左子节点2p，右子节点2p+1，如下所示
1-----------0
2--------0/--\1
4------0/-\1-2/-\3
...
2.左边没有节点，减去左边的空余，结果不变。如根节点的左节点不存在，则根节点的左节点的左节点可用0作索引，对结果无影响。
一次性总结二叉树中序遍历的morris算法，递归验证二叉搜索树，查找二叉搜索树中的众数的update函数。
中序遍历的递归算法实现方法很简单，不再赘述；递归算法实现看上面；morris算法的思路：遇到一个节点，首先判断其是否有左子树，若无，访问该节点，接着遍历其右子节点；若有左子树，找左子树的右下角节点(pre=cur->left;while(pre->right&&pre->right!=cur)pre=pre->right;)，找到左子树的右下角节点pre，然后判断pre->right是否为空，看前面的while循环条件，我们知道跳出循环时pre->right为空或者pre->right就是cur，若pre->right为空，说明中序遍历序列中cur的前继节点还没往后连上cur，设置pre->right=cur，遍历cur->left；若pre->right是cur，说明之前遇到cur时配置好了cur的前继节点，如今又遇到cur是从cur的前继节点过来的（前继节点的right），说明cur的左子树已遍历完成，该遍历cur了，遍历完cur，遍历cur->right。该算法的空间复杂度是O(1)，只需要cur和pre两个指针完成遍历，cur就是当前遇到或遍历的指针，pre是cur有左子树的情况下来探索右下角节点，然后pre->right=cur或者说明左子树遍历完成的，最后cur为空，遍历结束。
验证二叉搜索树的其中之一方法是得到树的中序遍历序列，看该序列是否为非递减序列。递归的方法是设置边界，左子树的所有节点的值均不大于根节点的值，右子树的所有节点的值均不小于根节点的值，设置子树的上下界即取值范围判断二叉搜索树的合法性。
查找二叉搜索树中的众数一方面考察中序遍历算法，另一方面考察如何update问题中的参数值。base是二叉搜索树节点取值边界外的最小值，若base==x，cnt++，否则base=x, cnt=1；接着若cnt==maxCnt, res.emplace_back(base)，否则若cnt>maxCnt, maxCnt=cnt,res=vector<int>{base}。中序遍历节点x时即update(x)。
二叉搜索树有n个节点，n个节点上的值分别是1，2，。。。，n，问这样的二叉搜索树有几个以及都长什么样。
这个问题牵涉到卡特兰数，我打算以后再探索这个数学概念。对于编程人员来说，用动态规划方法计算树的数量，递归获取树的结构。
dp[n+1]={0}，dp[0]=1,dp[1]=1，以根节点i为界，根节点的左子树有i-1个节点，右子树有n-i个节点，dp[i]表示i个节点形成的二叉搜索树的数量，for(int i=2;i<=n;i++)for(int j=1;j<=i;j++)dp[i]+=（以节点j为根节点的话）dp[j-1]（左子树的数量）*dp[i-j]（右子树的数量）;。
递归列举从1到n的二叉搜索树。以节点i为根节点，左子树是从1到i-1的二叉搜索树（递归构造，子问题），右子树是从i+1到n的二叉搜索树，如计算树的数量的方法，构造左子树和右子树的结构，相乘拼接。
相似的处理思路的题：我遇到这种题，觉得懵，左右互乘术。由数字、加号、减号和乘号组成的字符串，如果任意括上规范的括号后可能的取值。递归，以符号为界，左右两边字符串又是子问题，分治，原子问题是数字字符串。
参考链接：剑指 Offer 07. 重建二叉树
二叉树——后序遍历的递归与非递归算法
前序遍历的非递归算法
662. 二叉树最大宽度
94. 二叉树的中序遍历
98. 验证二叉搜索树
501. 二叉搜索树中的众数
96. 不同的二叉搜索树
95. 不同的二叉搜索树 II
241. 为运算表达式设计优先级