解题思路

1. 基本概念

二叉树的三种遍历方式是按照访问根节点的顺序来定义的：

  • 前序遍历：根节点 -> 左子树 -> 右子树
  • 中序遍历：左子树 -> 根节点 -> 右子树
  • 后序遍历：左子树 -> 右子树 -> 根节点

2. 图解示例

     1
   /   \
  2     3
 / \   / \
4   5 6   7

前序遍历过程：

  1. 先访问根节点 1
  2. 然后访问左子树 (2,4,5)
  3. 最后访问右子树 (3,6,7) 结果：1,2,4,5,3,6,7

中序遍历过程：

  1. 先访问左子树 (4,2,5)
  2. 然后访问根节点 1
  3. 最后访问右子树 (6,3,7) 结果：4,2,5,1,6,3,7

后序遍历过程：

  1. 先访问左子树 (4,5,2)
  2. 然后访问右子树 (6,7,3)
  3. 最后访问根节点 1 结果：4,5,2,6,7,3,1

3. 解题步骤

  1. 创建三个列表分别存储三种遍历结果
  2. 对每种遍历：
    • 如果节点为空，返回
    • 按照对应顺序访问根节点和递归遍历左右子树
  3. 将三个列表组合成二维数组返回

4. 注意事项

  • 处理空树的情况
  • 注意递归的终止条件
  • 确保遍历顺序正确
  • 注意左右子树的访问顺序

代码

class Solution {
public:
    vector<int> preOrder, inOrder, postOrder;  // 存储三种遍历结果
    
    // 前序遍历：根->左->右
    void preOrderTraversal(TreeNode* root) {
        if (!root) return;
        preOrder.push_back(root->val);  // 先访问根节点
        preOrderTraversal(root->left);   // 再遍历左子树
        preOrderTraversal(root->right);  // 最后遍历右子树
    }
    
    // 中序遍历：左->根->右
    void inOrderTraversal(TreeNode* root) {
        if (!root) return;
        inOrderTraversal(root->left);    // 先遍历左子树
        inOrder.push_back(root->val);    // 再访问根节点
        inOrderTraversal(root->right);   // 最后遍历右子树
    }
    
    // 后序遍历：左->右->根
    void postOrderTraversal(TreeNode* root) {
        if (!root) return;
        postOrderTraversal(root->left);   // 先遍历左子树
        postOrderTraversal(root->right);  // 再遍历右子树
        postOrder.push_back(root->val);   // 最后访问根节点
    }
    
    vector<vector<int>> threeOrders(TreeNode* root) {
        // 清空结果数组
        preOrder.clear();
        inOrder.clear();
        postOrder.clear();
        
        // 执行三种遍历
        preOrderTraversal(root);
        inOrderTraversal(root);
        postOrderTraversal(root);
        
        // 返回结果
        return {preOrder, inOrder, postOrder};
    }
};


import java.util.*;

public class Solution {
    private List<Integer> preOrder = new ArrayList<>();
    private List<Integer> inOrder = new ArrayList<>();
    private List<Integer> postOrder = new ArrayList<>();
    
    // 前序遍历
    private void preOrderTraversal(TreeNode root) {
        if (root == null) return;
        preOrder.add(root.val);
        preOrderTraversal(root.left);
        preOrderTraversal(root.right);
    }
    
    // 中序遍历
    private void inOrderTraversal(TreeNode root) {
        if (root == null) return;
        inOrderTraversal(root.left);
        inOrder.add(root.val);
        inOrderTraversal(root.right);
    }
    
    // 后序遍历
    private void postOrderTraversal(TreeNode root) {
        if (root == null) return;
        postOrderTraversal(root.left);
        postOrderTraversal(root.right);
        postOrder.add(root.val);
    }
    
    public int[][] threeOrders(TreeNode root) {
        // 清空结果列表
        preOrder.clear();
        inOrder.clear();
        postOrder.clear();
        
        // 执行三种遍历
        preOrderTraversal(root);
        inOrderTraversal(root);
        postOrderTraversal(root);
        
        // 转换为二维数组
        int[][] result = new int[3][];
        result[0] = preOrder.stream().mapToInt(Integer::intValue).toArray();
        result[1] = inOrder.stream().mapToInt(Integer::intValue).toArray();
        result[2] = postOrder.stream().mapToInt(Integer::intValue).toArray();
        
        return result;
    }
}

class Solution:
    def threeOrders(self, root: TreeNode) -> List[List[int]]:
        pre_order = []
        in_order = []
        post_order = []
        
        # 前序遍历
        def pre_traverse(node):
            if not node:
                return
            pre_order.append(node.val)  # 根
            pre_traverse(node.left)     # 左
            pre_traverse(node.right)    # 右
            
        # 中序遍历
        def in_traverse(node):
            if not node:
                return
            in_traverse(node.left)      # 左
            in_order.append(node.val)   # 根
            in_traverse(node.right)     # 右
            
        # 后序遍历
        def post_traverse(node):
            if not node:
                return
            post_traverse(node.left)     # 左
            post_traverse(node.right)    # 右
            post_order.append(node.val)  # 根
            
        # 执行三种遍历
        pre_traverse(root)
        in_traverse(root)
        post_traverse(root)
        
        return [pre_order, in_order, post_order]

算法及复杂度分析

  • 算法:递归，树的遍历
  • 时间复杂度：，每个节点都需要访问一次
  • 空间复杂度：，h为树的高度，递归调用栈的空间