题解 | #实现二叉树先序，中序和后序遍历#

思路

1. 二叉树的前序遍历的顺序：根节点-->左子树-->右子树；
2. 中序遍历的顺序：左子树-->根结点-->右子树；
3. 后序遍历的顺序：左子树-->右子树-->根结点。

这是一个典型的递归问题。递归问题的一个关键就是退出递归的条件。

中序遍历是从根节点开始的，因此采用这样一个访问顺序：

1. 访问节点；
2. 左侧递归；
3. 右侧递归。

直到没有左节点的时候退出递归。

中序遍历则是首先去进行左侧递归，然后访问，然后右侧递归：

1. 左侧递归；
2. 访问节点；
3. 右侧递归。

后序遍历是：

1. 左侧递归；
2. 右侧递归；
3. 访问节点。

代码实现

import java.util.ArrayList;
import java.util.List;


public class Solution {
    List<Integer> preorderList = new ArrayList<>();
    List<Integer> midorderList = new ArrayList<>();
    List<Integer> backorderList = new ArrayList<>();

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode();
        treeNode.val = 1;
        treeNode.left = new TreeNode();
        treeNode.right = new TreeNode();
        treeNode.left.val = 2;
        treeNode.right.val = 3;
        Solution solution = new Solution();
        int[][] arr = solution.threeOrders(treeNode);
        System.out.println(arr[0][0]);
    }

    /**
     * @param root TreeNode类 the root of binary tree
     * @return int整型二维数组
     */
    public int[][] threeOrders(TreeNode root) {
        // write code here
        preorder(root);
        midorder(root);
        backorder(root);
        int[][] a = {
                preorderList.stream().mapToInt(Integer::valueOf).toArray(),
                midorderList.stream().mapToInt(Integer::valueOf).toArray(),
                backorderList.stream().mapToInt(Integer::valueOf).toArray()
        };
        return a;
    }

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

    }

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

    }

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

    }
}

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
}