NC45：实现二叉树先序，中序和后序遍历

题解

List<Integer> pre = new ArrayList<>();
    List<Integer> in = new ArrayList<>();
    List<Integer> post = new ArrayList<>();

    public int[][] threeOrders (TreeNode root) {
        // write code here
        if (root == null) return new int[][] {{}};
        List<List<Integer>> ans = new ArrayList<>();
        preOrder(root);
        inOrder(root);
        postOrder(root);
        ans.add(pre);
        ans.add(in);
        ans.add(post);
        int[][] res = new int[ans.size()][ans.get(0).size()];
        for (int i = 0; i < ans.size(); i++) {
            for (int j = 0; j < ans.get(0).size(); j++) {
                res[i][j] = ans.get(i).get(j);
            }
        }
        return res;
    }

    private void preOrder(TreeNode root) {
        if (root == null) return;
        pre.add(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }

    private void inOrder(TreeNode root) {
        if (root == null) return;
        inOrder(root.left);
        in.add(root.val);
        inOrder(root.right);
    }

    private void postOrder(TreeNode root) {
        if (root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        post.add(root.val);
    }

参考知识

二叉树遍历：递归方法：

 public static class Node{
        public int value;
        public Node left;
        public Node right;

        public Node(int data){
            this.value=data;
        }
    }
// 递归版先中后序遍历
    public static void preOrderRecur(Node head){
        if(head==null){
            return;
        }
        System.out.print(head.value+" ");
        preOrderRecur(head.left);
        preOrderRecur(head.right);
    }
    public static void inOrderRecur(Node head){
        if(head==null){
            inOrderRecur(head.left);
            System.out.print(head.value+" ");
            inOrderRecur(head.right);
        }
    }
    public static void posOrderRecur(Node head){
        if(head==null){
            return;
        }
        posOrderRecur(head.left);
        posOrderRecur(head.right);
        System.out.print(head.value+" ");
    }

二叉树遍历：非递归方法：

/*
* 先序遍历
* 往栈中压入根结点
* 弹出栈中一个结点并打印
* 压入刚弹出结点的右结点和左结点
* 弹出栈中一个结点并打印
*/
    public static void preOrderUnRecur(Node head){
        System.out.print("preOrder: ");
        if(head!=null){
            Stack<Node> stack=new Stack<Node>();
            stack.add(head);  //往栈中压入根结点
            while(!stack.isEmpty()){
                head=stack.pop(); //弹出栈中一个结点并打印,复用了head 
                System.out.print(head.value+" ");
                if(head.right!=null){
                    stack.push(head.right);
                }
                if(head.left!=null){
                    stack.push(head.left);
                }
            }
        }
        System.out.println();
    }
/*
 * 中序遍历
 * 当前结点不为空时，压入当前结点，当前结点指针向它左结点移动
 * 当前结点为空、栈不为空时，弹出栈结点并打印，当前结点指针向栈结点的右结点移动
*/
    public static void inOrderUnrecur(Node head){
        System.out.print("inOrder: ");
        if(head!=null){
            Stack<Node> stack=new Stack<Node>();
            while(!stack.isEmpty() || head!=null){
                if(head!=null){
                    stack.push(head);
                    head=head.left;
                }
                else{
                    head=stack.pop();
                    System.out.print(head.value+" ");
                    head=head.right;
                }
            }
        }
        System.out.println();
    }
 /*
 * 后序遍历
 * 由前面的先序遍历，中左右，改为中右左，然后放入栈中逆序，得到左右中，即后序遍历
 */
    public static void posOrderUnRecur(Node head){
        System.out.print("posOrder: ");
        if(head!=null){
            Stack<Node> s1=new Stack<Node>();
            Stack<Node> s2=new Stack<Node>();
            s1.push(head);
            if(!s1.isEmpty()){
                head=s1.pop();
                s2.push(head);
                if(head.left!=null){
                    s1.push(head.left);
                }
                if(head.right!=null){
                    s1.push(head.right);
                }
            }
            while(!s2.isEmpty()){
                System.out.print(s2.pop().value+" ");
            }
        }
        System.out.println();
    }