题解 | #二叉树的中序遍历#1、递归2、单栈3、Morris遍历

	//1.递归遍历
    public int[] inorderTraversal1 (TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        process(root,list);
        int[] res = new int[list.size()];
        for(int i = 0;i<list.size();i++){
            res[i] = list.get(i);
        }
        return res;
    }
    public void process(TreeNode root,ArrayList<Integer> list){
        if(root==null) return;
        process(root.left,list);
        list.add(root.val);
        process(root.right,list);
    }
    //2.单栈遍历
    public int[] inorderTraversal2 (TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        ArrayList<Integer> list = new ArrayList<>();
        TreeNode cur = root;
        while(!stack.isEmpty()||cur!=null){
            if(cur!=null){
                stack.push(cur);
                cur = cur.left;
            }else{
                TreeNode top = stack.pop();
                list.add(top.val);
                cur = top.right;
            }
        }
        int N = list.size();
        int[] res = new int[N];
        for(int i = 0;i<N;i++){
            res[i] = list.get(i);
        }
        return res;
    }
    //3.morris遍历
    public int[] inorderTraversal (TreeNode root) {
        //每到一个节点，若是有左子树，则找得到左子树最右节点，让它的right指向cur，第二次则指回null
        TreeNode cur = root;
        ArrayList<Integer> list = new ArrayList<>();
        while(cur!=null){
            if(cur.left!=null){
                TreeNode leftTreeMostRight = cur.left;
                while(leftTreeMostRight.right!=null&&leftTreeMostRight.right!=cur){
                    leftTreeMostRight = leftTreeMostRight.right;
                }
                if(leftTreeMostRight.right==null){
                    leftTreeMostRight.right = cur;
                    cur = cur.left;
                    continue;
                }
                leftTreeMostRight.right = null;
            }
            list.add(cur.val);
            cur = cur.right;
        }
        int N = list.size();
        int[] res = new int[N];
        for(int i = 0;i<N;i++){
            res[i] = list.get(i);
        }
        return res;
    }