94.二叉树的中序遍历

借这个题目延展一下，一次写完前序，后序，中序的递归和非递归写法

一. 递归解法

如下所示，只要调整dfs遍历顺序就可以轻松得到先序，中序，后序的遍历结果了；

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res= new LinkedList<>();
        dfs(res,root);
        return res;
    }

    private void dfs(List<Integer> res, TreeNode root) {
        if (root==null){
            return;
        }
        dfs(res,root.left);
        res.add(root.val);
        dfs(res,root.right);
    }
}

二.非递归解法

1.先序

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res= new LinkedList<>();
        Stack<TreeNode> stack=new Stack<>();
        if (root==null){
            return res;
        }
        //打印，左，右
        stack.push(root);

        while (!stack.isEmpty()){
            TreeNode curr = stack.pop();
            res.add(curr.val);
            //栈先进后出，我们要后面打印右树，因此先把右树放进去
            if (curr.right!=null){
                stack.push(curr.right);
            }

            if (curr.left!=null){
                stack.push(curr.left);
            }
        }
        return res;
    }

中序

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res= new LinkedList<>();
        Stack<TreeNode> stack=new Stack<>();

        while (root!=null||stack.size()>0){
            //直到不能继续向左再停止
            if (root!=null){
                stack.add(root);
                root=root.left;
                //如果root为null说明stack最新的一个结点无左节点，
                // 因此直接先打印本节点，再迭代调用B结点
            }else {
                TreeNode pop = stack.pop();
                res.add(pop.val);
                root=pop.right;
            }
        }
        return res;
    }

后序
前面俩我都是用的栈方式，后序遍历我也提供一个栈方式；
后续遍历跟先序遍历比较像,这里是定义了两个栈,把打印的放在打印栈stack2里

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res= new LinkedList<>();
        if (root==null){
            return res;
        }
        //先序栈
        Stack<TreeNode> stack1=new Stack<>();
        //打印栈
        Stack<Integer> stack2=new Stack<>();
        stack1.push(root);
        while (!stack1.isEmpty()){
            TreeNode pop = stack1.pop();
            stack2.push(pop.val);
            if (pop.left!=null){
                stack1.push(pop.left);
            }

            if (pop.right!=null){
                stack1.push(pop.right);
            }
        }

        //打印
        while (!stack2.isEmpty()){
            res.add(stack2.pop());
        }

        return res;
    }

跟leetcode学到，这里再提供一个高效的，双向链表版本

{
            LinkedList<Integer> res = new LinkedList<>();
            if (root == null) {
                return res;
            }
            Stack<TreeNode> stack = new Stack<>();

            while (!stack.isEmpty() || root != null) {
                while (root != null) {
                    res.addFirst(root.val);
                    stack.push(root);
                    root = root.right;
                }

                if (!stack.isEmpty()) {
                    root = stack.pop();
                    root = root.left;
                }
            }
            return res;
        }