Tree

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途中是不存在比较的