PreOrder: Root, left, right
InOrder: Left, root, right
PostOrder: Left, right, root
首先递归的方法是很简单的
public void inorder( List result , TreeNode root) {
if (root == null) {
return;
}
inorder(result, root.left);
result.add(root.val);
inorder(result, root.right);
}
类似的前序和后续，只是交换下调用的顺序就可以轻松完成。
那这里我们需要了解的是，如何不用递归来实现前中后序的遍历
前序最简单：
思路：用一个Stack，每次先输出根，然后加入根的右孩子，加入根的左孩子，这里注意的是为什么先加右边再加左边，因为栈是先进后出规则。而那为什么不能用队列来实现先进左孩子再进右孩子呢，因为我们是处理完成整个左孩子再处理右孩子，而不是一层层的孩子去处理。
中序稍难：
思路：首先是push根，然后向左先找，直到左边是Null了，我们弹栈，并且往右边找。
while(!stack.isEmpty() || root != null) {
if (root != null) {
stack.push(root);
root = root.left;
} else{
root = stack.pop();
result.add(root.val);
root = root.right;
}
}
#Medium 98. Validate Binary Search Tree
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
思路1：可以看每一个左子树的最后下角是不是大于根，每个右子树的最左下角是不是小于根，并且是他们的孩子也满足改条件递归下去即可。
思路2：满足二叉搜索树的重大性质！！！就是中序遍历是从小到大来的
#95. Unique Binary Search Trees II
Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1...n.
For example,
Given n = 3, your program should return all 5 unique BST's shown below.
思路：利用递归，每次新建一个List<TreeNode>开始start到end遍历，分别作为根的可能性，然后算左边的List和后边的List,把所有可能找到，返回这个List. 注意我们这里都是找的List，返回的是所有可能，所以需要双层遍历来得到树
#Hard 99. Recover Binary Search Tree
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
思路：因为BST必须是满足的中序遍历是按照升序排列，所以我们可以对树进行中序遍历，一旦pop时候，发现比之前那个数是小的，那我们就要记录下这个错误的Node，然后对于这两个Node的val交换即可、
注意:Previous 是每次pop之后指向的，并且每次Pop之后才去previous比较，在push途中是不存在比较的
