二叉树前中后序遍历

灰太狼 2022-12-03 13:22 156阅读 0赞

# 二叉树前中后序遍历 #

## 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;
    }