记录树的前中后序和层次遍历的写法。

一、前序遍历

1.递归写法

  public void preOrder(){
        preOrder(root);
    }
    private void preOrder(TreeNode node){
        if(node == null)
            return;
        System.out.println(node.val);
        //先打印的是该节点，在访问左节点和右节点所以是前序
        preOrder(node.left);
        preOrder(node.right);
    }

2.非递归写法

 public void preOrder1(TreeNode root){
        if(root == null)
            return ;
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()) {
            Node temp = stack.pop();
            System.out.println(temp.val);
            if(temp.right != null)
                stack.push(temp.right);
            if(temp.left != null)
                stack.push(temp.left);
        }
        return ;
    }

二、中序遍历

1.递归写法

 // 二分搜索树的中序遍历
    public void inOrder(){
        inOrder(root);
    }
    // 中序遍历以node为根的二分搜索树, 递归算法
    private void inOrder(TreeNode node){
        if(node == null)
            return;
        inOrder(node.left);
        System.out.println(node.val);
        inOrder(node.right);
    }

2.非递归写法

写法相比于前序的非递归要稍微复杂些，因为中序需要一直压节点，因此需要反复判断。本写法的遍历结果用List存放。
写法1：只要当前节点不为空，每次都压入当前节点。当前节点为空，说明该节点的父节点就是叶子节点，且此时栈顶节点就是该空节点的父节点，因此弹出后就可加入到队列中（打印），然后去遍历该父节点的右子节点。

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            if (root != null) { 
                stack.push(root);
                root = root.left;
            } else {             
                TreeNode node = stack.pop();
                res.add(node.val);//这里打印
                root = node.right;
            }
        }
        return res;
    }

第2个写法，压入当前节点的左子节点或者右子节点（这里我的idea上写法方法有误，要补上最后一个else）

 public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root==null)
            return res;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode temp = root;//辅助节点
        stack.push(temp);
        while(stack.isEmpty() == false) {
            //只要你有左孩子，就将左孩子压入栈中
            if(temp!=null && temp.left!=null) {
                stack.add(temp.left);
                temp = temp.left;
            }else {
                temp = stack.pop();//弹出栈顶节点  左孩子--->根节点
                res.add(temp.val);//访问
                if(temp!=null && temp.right!=null) {
//如果栈顶元素有右孩子的话，将有节点压入栈中
                    stack.add(temp.right);
                    temp = temp.right;
                }else
                    temp=null;
//这个else不补上，会导致没有右子节点的节点，会又被访问一次
            }
        }
        return res;
    }

三、后序遍历

1.递归写法

    public void postOrder(){
        postOrder(root);
    }
    private void postOrder(Node node){
        if(node == null)
            return;
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.val);
    }

2.非递归写法

主要记录2个写法。
第一个写法：
前序是根左右，中序是左根右，后序是左右根。我们知道前序的根左右很好写，相应的我们写一个根右左也很好写，我们再用一个栈将根右左变成左右根，这样就形成了后序遍历。

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList();
        if (root == null)
            return list;
        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        s1.push(root);
        while (!s1.isEmpty()) {
            root = s1.pop();
            s2.push(root);
            if (root.left != null) {
                s1.push(root.left);
            }
            if (root.right != null) {
                s1.push(root.right);
            }
        }
        while (!s2.isEmpty()) {
            list.add(s2.pop().val);
        }
        return list;
    }

写法2：
考虑到根节点是最后遍历到的，因此我们需要知道，某个节点访问完后，到底是访问这个节点的父节点，还会这个节点的兄弟节点（右节点），如果不加判断，就不知道下一个节点应该怎么访问，因为，需要一个变量或者数据结构去记录一些遍历的信息。

 public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        TreeNode last = null;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.peek();
//如果某个节点没有右节点，或者右边节点访问过了，那么就将该节点添加到结果集，并弹出
            if (curr.right == null || curr.right == last) {
                res.add(curr.val);
                stack.pop();
                last = curr;//用last记录这个弹出的节点（已访问过）
                curr = null;
            } else {//如果栈顶元素还有右子节点，就得入栈
                curr = curr.right;
            }
        }
        return res;
    }

四、层序遍历

一般是用队列

public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode nowNode = q.poll();
            res.add(nowNode.val);
            if (nowNode.left != null) {
                q.add(nowNode.left);
            }
            if (nowNode.right != null) {
                q.add(nowNode.right);
            }
        }

        return res;
    }