01、二叉树遍历详解

遍历二叉树

二叉树的遍历指从根节点出发,按照某种次序依次访问二叉树的所有节点,使得每个节点都被访问且访问一次.

我们下面介绍二叉树的几种遍历方法及其对应的题目, 前序遍历, 中序遍历 , 后序遍历 , 层序遍历 .

前序遍历

前序遍历的顺序是, 对于树中的某节点,先遍历该节点,然后再遍历其左子树,最后遍历其右子树.

只看文字有点生硬, 下面我们直接看动画吧

前序遍历

测试题目: leetcode 144. 二叉树的前序遍历

代码实现(递归版)

#include <vector>

// 二叉树节点定义
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    std::vector<int> preorderTraversal(TreeNode* root) {
        std::vector<int> arr;  // 存储遍历结果，对应Java的ArrayList
        preorder(root, arr);   // 调用递归函数
        return arr;
    }

private:
    // 递归辅助函数：前序遍历（根→左→右）
    void preorder(TreeNode* root, std::vector<int>& arr) {
        if (root == nullptr) {  // 空节点直接返回
            return;
        }
        arr.push_back(root->val);  // 先访问根节点
        preorder(root->left, arr); // 递归遍历左子树
        preorder(root->right, arr);// 递归遍历右子树
    }
};

时间复杂度 : O(n) 空间复杂度 : O(n) 为递归过程中栈的开销,平均为 O(logn),但是当二叉树为斜树时则为 O(n)

为了控制文章篇幅, 二叉树的迭代遍历形式, 会在下篇文章进行介绍。

中序遍历

中序遍历的顺序是, 对于树中的某节点,先遍历该节点的左子树, 然后再遍历该节点, 最后遍历其右子树

继续看动画吧, 如果有些遗忘或者刚开始学数据结构的同学可以自己模拟一下执行步骤.

测试题目: leetcode 94 题 二叉树的中序遍历

代码实现(递归版)

#include <vector>

// 二叉树节点定义
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    std::vector<int> inorderTraversal(TreeNode* root) {
        std::vector<int> res;  // 存储遍历结果，对应Java的ArrayList
        inorder(root, res);    // 调用递归辅助函数
        return res;
    }

private:
    // 递归辅助函数：中序遍历（左→根→右）
    void inorder(TreeNode* root, std::vector<int>& res) {
        if (root == nullptr) {  // 空节点直接返回
            return;
        }
        inorder(root->left, res);  // 先递归遍历左子树
        res.push_back(root->val);  // 访问当前根节点
        inorder(root->right, res); // 最后递归遍历右子树
    }
};

时间复杂度 : O(n) 空间复杂度 : O(n)

后序遍历

后序遍历的顺序是, 对于树中的某节点, 先遍历该节点的左子树, 再遍历其右子树, 最后遍历该节点.

哈哈,继续看动画吧,看完动画就懂啦.

测试题目: leetcode 145 题 二叉树的后序遍历

代码实现(递归版)

#include <vector>

// 二叉树节点定义
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    std::vector<int> postorderTraversal(TreeNode* root) {
        std::vector<int> res;  // 存储遍历结果，对应Java的ArrayList
        postorder(root, res);  // 调用递归辅助函数
        return res;
    }

private:
    // 递归辅助函数：后序遍历（左→右→根）
    void postorder(TreeNode* root, std::vector<int>& res) {
        if (root == nullptr) {  // 空节点直接返回
            return;
        }
        postorder(root->left, res);   // 先递归遍历左子树
        postorder(root->right, res);  // 再递归遍历右子树
        res.push_back(root->val);     // 最后访问当前根节点
    }
};

时间复杂度 : O(n) 空间复杂度 : O(n)