思路
- 二叉树的前序遍历的顺序:根节点-->左子树-->右子树;
- 中序遍历的顺序:左子树-->根结点-->右子树;
- 后序遍历的顺序:左子树-->右子树-->根结点。
这是一个典型的递归问题。递归问题的一个关键就是退出递归的条件。
中序遍历是从根节点开始的,因此采用这样一个访问顺序:
- 访问节点;
- 左侧递归;
- 右侧递归。
直到没有左节点的时候退出递归。
中序遍历则是首先去进行左侧递归,然后访问,然后右侧递归:
- 左侧递归;
- 访问节点;
- 右侧递归。
后序遍历是:
- 左侧递归;
- 右侧递归;
- 访问节点。
代码实现
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; }