1. 二叉树的遍历

二叉树的遍历可以有三种 ： 先序、 中序、 后序遍历 。先序是根左右 ，中序是左根右 ，后序是左右根。 这三种遍历方式可以使用递归实现，也可以不用递归（自己来压栈代替系统压栈）。

1.1 递归实现

为了记忆方便，可以统一使用 “递归序”来实现三种次序的遍历 。 看如下的代码

public class Traverse {
    public void myTraverse(TreeNode head){
        //process1
        if(head == null ) return;
        //process1
        myTraverse( head.left);
        //process2
        //process2
        myTraverse( head.right);
        //process3
        //process3

    }
}

如果在process1之间，执行代码就是先序遍历，在process2之间，执行代码就是中序遍历，在process3之间，执行代码就是中序遍历，这样代码就非常容易实现了。下面是按照递归序改造的先序遍历在leetcode上执行，因为不是void型返回结果，而是把遍历结果插入到一个list中，所以代码中带了一个list型的参数，但是不影响主体。

class Solution {

    //通过递归序完成先序遍历
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> outPut = new ArrayList<>() ; 
        Traversal(root,outPut) ;
        return outPut ; 
    }

    public void Traversal(TreeNode root, List<Integer> outPut){
        if(root == null) return ;
        outPut.add(root.val) ;
        Traversal(root.left, outPut) ;
        Traversal(root.right, outPut) ;
    }

}

1.2 非递归实现 ：

非递归实现三种遍历方式，使用额外栈来实现，这样容易记忆 。

1.2.1 先序遍历 ：

先序遍历使用栈，要记住下边几个步骤 ：

1.初始化将树的根节点压栈 ；
2.从栈中弹出一个节点 ；
3.开始做遍历操作（例如：打印等等）
4.把这个弹出的节点的子树压栈（先右后左，如果有的话）
5.循环执行 2~3 步骤。

下面是使用 栈完成的非递归前序遍历 ：

    //通过非递归序完成先序遍历
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> outPut = new ArrayList<>() ;
        if(root != null){
            Stack<TreeNode> usStack = new Stack() ;
            usStack.push(root);
            while(!usStack.isEmpty()){
                TreeNode cp = usStack.pop();
                outPut.add(cp.val) ;
                if(cp.right != null) usStack.push(cp.right);
                if(cp.left != null) usStack.push(cp.left);
            }

        }
        return outPut;
    }

1.2.2 后序遍历 ：

上边前序遍历，使用了一个栈，压栈顺序是根、右、左 ，输出顺序是 根、左、右（也就是前序遍历）。这时，在压栈时，如果我先压左再压右，那么输出顺序就变成了 根、右、 左。
这时，我再使用一个辅助收集栈，输出时候不打印，而是放入收集栈，最后再输出时，就变成了后序遍历了。 相比于前序遍历得到立即打印，这个就变成了都压栈完后，一起打印就得到了后序遍历了。
这样流程就梳理为下边的样子 ：

1.初始化将树的根节点压原始栈 ；
2.从原始栈中弹出一个节点，记为cur ；
3.cur压入收集栈
4.把这个cur的子树压入原始栈（先左后右，如果有的话）
5.循环执行 2~4 步骤。
6.将收集栈统一打印。

下边是后序遍历的非递归实现 ：

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> outPut = new ArrayList<>() ;
        if(root != null){
            Stack<TreeNode> oriStack = new Stack() ;
            Stack<TreeNode> collectStack = new Stack() ;
            oriStack.push(root);
            while(!oriStack.isEmpty()){
                TreeNode curr = oriStack.pop();
                collectStack.push(curr);
                //原始栈的压栈次序是先左后右，与先序遍历不一样
                if(curr.left != null) oriStack.push(curr.left);
                if(curr.right != null) oriStack.push(curr.right);
            }
            while (!collectStack.isEmpty()){
                outPut.add(collectStack.pop().val);
            }
        }
        return outPut;
    }
}

1.2.3 中序遍历 ：

中序遍历的算法有所不同 ，使用一个栈就可以完成。 流程如下 ：

1.初始化将树的根节点压栈 ；
2.对于每一棵子树，左边界依次压栈，直到压到为NULL为止。
3.弹出栈顶节点，弹出时打印。
4.对弹出节点的右子树重复，2-3过程。

下面是 中序遍历的java代码实现（非递归）：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> outPut = new ArrayList<>();
        if (root != null) {
            Stack<TreeNode> oriStack = new Stack();
            while(!oriStack.isEmpty() || root !=null){
                if(root != null){
                    oriStack.push(root) ;
                    root = root.left ;
                }
                else
                {
                    root = oriStack.pop() ;
                    outPut.add(root.val) ;
                    root = root.right ;
                }
            }
        }
        return outPut ;
    }
}

2. 搜索二叉树

如何判断一棵树是搜索二叉树 ，要完成这个问题，首先需要了解什么是搜索二叉树 ？

对于一棵搜索二叉树而言，每一个节点的左子树都比右子树小 。也就是说 左子树节点 < 根节点 < 右子树节点。经典的搜索二叉树中没有重复值的节点。

其实比较简单，只要做“中序遍历” 后，得到的序列是单调上升，即可表示是一棵搜索二叉树。