Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

计算后缀表达式。我们一般看到的数学表达式就是中缀表达式，也就是将符号放在两个数字之间。后缀表达式也就是将运算符放在相应数字的后面。后缀表达式相当于树中的后序遍历。

将一个字符串逐渐分解为一个叶节点为单个字母的树。允许对非叶结点的两个子节点进行旋转，且允许对多个非叶节点进行子节点的旋转操作。将该操作生成的新字符串成为scrambled string。现在输入两个字符串，判断该两个字符串是否是scrambled string。

在这里和其它题目不一样的是，并非从根节点到叶节点的一条路径，而是从任意一个节点到任意一个节点的路径。其实在这里我们通过递归的方法可以发现以下几种场景：

如果只是单纯的计算二叉树的数量，其实这就完全转化成了一道规律题。我们可以从1开始寻找规律。1： 11，2： 12， 211，2，3：123，132，213，312，321

乍一看这题可以通过递归的方式来求解。我们可以同时判断当前下标s1和s2的元素是不是和s3当前下标的元素相同。如果相同，就进入下一轮递归。代码如下：

通过栈的形式同样可以实现比较。将需要进行比较的节点依次压入栈中。每次从栈中取出两个进行比较的节点比较。有点像level traversal的思路。

其实在数据结构的教材中为了说明栈和队列的使用，分别举的就是中序遍历和水平遍历的例子。在这里我们同样可以使用队列的先进先出的机制将同一行的元素读入后，再逐个读出，并在同时插入下一行中的元素。

我们可以发现，如果已知当前节点的值val以及取值的上下限upper，lower，那么左子节点的取值范围就是(lower, val),右子节点的取值范围就是(val, upper)。由此出发递归判断，时间复杂度为O(n)因为每个节点只需要遍历一次。

如果了解中序遍历的同学可以知道，一颗二叉查找树的中序遍历结果应当是一个数值有小到大递增的数组。正因为中序遍历是指先遍历左子树，接着遍历中间节点，再遍历右子树，恰好和查找树的值递增顺序相同。因此在这里我们采用栈的方式实现中序遍历，通过研究中序遍历是否递增来判断二叉查找树是否符合规则。代码如下：

如果了解中序遍历的同学可以知道，一颗二叉查找树的中序遍历结果应当是一个数值有小到大递增的数组。正因为中序遍历是指先遍历左子树，接着遍历中间节点，再遍历右子树，恰好和查找树的值递增顺序相同。因此在这里我们采用栈的方式实现中序遍历，通过研究中序遍历是否递增来判断二叉查找树是否符合规则。代码如下：

这里需要利用栈的数据结构。如果当前节点存在左子节点，则继续遍历左子树直到最后一个左子节点。然后依次处理栈中的元素。如果栈顶元素有右子节点，则将其右子节点压入栈中作为root，再继续遍历root的左子节点。当root和stack都为空时，遍历结束。