二叉树前中后序遍历

1、参考资料

https://www.nowcoder.com/practice/a9fec6c46a684ad5a3abd4e365a9d362

https://blog.csdn.net/qq407388356/article/details/79489270

2、题目要求

题目描述

分别按照二叉树先序，中序和后序打印所有的节点。

示例

输入

{1,2,3}

输出

[[1,2,3],[2,1,3],[2,3,1]]

3、代码思路

参照二叉树的深度优先遍历，只不过之前我们需要输出节点值，这次需要将遍历的顺序存储在 ArrayList 中

4、代码实现

代码

class Solution { /** * @param root TreeNode类 the root of binary tree * @return int整型二维数组 */ public int[][] threeOrders(TreeNode root) { generateThreeOrdersList(root); int n = preOrder.size(); int[][] orders = new int[3][n]; for (int i = 0; i < preOrder.size(); i++) { orders[0][i] = preOrder.get(i); orders[1][i] = infixOrder.get(i); orders[2][i] = postOrder.get(i); } return orders; } private List<Integer> preOrder = new ArrayList<>(); // 保存前序遍历的结果 private List<Integer> infixOrder = new ArrayList<>(); // 保存中序遍历的结果 private List<Integer> postOrder = new ArrayList<>(); // 保存后序遍历的结果 /** * dfs 遍历二叉树 * @param curNode 当前正在遍历的节点 */ private void generateThreeOrdersList(TreeNode curNode) { // 如果节点为空，则证明已经遍历到最深层，返回即可 if (curNode == null) { return; } // 前序遍历的结果 preOrder.add(curNode.val); // 进行左递归 generateThreeOrdersList(curNode.left); // 中序遍历的结果 infixOrder.add(curNode.val); // 进行右递归 generateThreeOrdersList(curNode.right); // 后序便利的结果 postOrder.add(curNode.val); } } class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; }