数据结构与算法面试题：实现二叉树的遍历（前序、中序、后序、层序）。

GeekLiHua

发布于 2025-01-21 15:06:02

10200

代码可运行

文章被收录于专栏：JavaJava

运行总次数：0

代码可运行

数据结构与算法面试题：实现二叉树的遍历（前序、中序、后序、层序）。

简介：数据结构与算法面试题：实现二叉树的遍历（前序、中序、后序、层序）。

算法思路

算法思路：

二叉树遍历是树的基础运算，主要包括前序遍历、中序遍历、后序遍历和层序遍历。其中，前序、中序和后序遍历即为深度优先搜索（DFS），而层序遍历则为广度优先搜索（BFS）。
对于遍历，我们可以使用递归或者迭代的方式来实现。递归方式比较直观，并且代码简单易懂；而迭代方式需要借助栈等数据结构，看上去比较复杂，但实际上在实际编程工作中也占有重要地位。

接下来给出C++实现的代码，注释详细：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) { // 前序遍历
        vector<int> res; // 存储遍历结果的数组
        stack<TreeNode*> stk; // 储存访问节点的栈
        if (root != NULL) stk.push(root); // 将根节点压入栈
        while (!stk.empty()) { // 在栈不为空时循环
            TreeNode* p = stk.top(); // 取栈顶元素
            stk.pop(); // 弹出栈顶元素
            res.push_back(p->val); // 将当前节点的值加入到数组中
            if (p->right != NULL) stk.push(p->right); // 先将右子节点压入栈
            if (p->left != NULL) stk.push(p->left); // 再将左子节点压入栈中
        }
        return res;
    }

    vector<int> inorderTraversal(TreeNode* root) { // 中序遍历
        vector<int> res; // 存储遍历结果的数组
        stack<TreeNode*> stk; // 储存访问节点的栈
        TreeNode* p = root;
        while (p != NULL || !stk.empty()) { // 在有可访问的节点时循环
            while (p != NULL) { // 一直沿左子节点走到最底端
                stk.push(p);
                p = p->left;
            }
            p = stk.top(); // 取栈顶元素
            stk.pop(); // 弹出栈顶元素
            res.push_back(p->val); // 将当前节点的值加入到数组中
            p = p->right; // 访问右子节点
        }
        return res;
    }

    vector<int> postorderTraversal(TreeNode* root) { // 后序遍历
        vector<int> res; // 存储遍历结果的数组
        stack<TreeNode*> stk; // 储存访问节点的栈
        if (root != NULL) stk.push(root); // 将根节点压入栈
        while (!stk.empty()) { // 在栈不为空时循环（前序遍历的逆序）
            TreeNode* p = stk.top(); // 取栈顶元素
            stk.pop(); // 弹出栈顶元素
            res.insert(res.begin(), p->val); // 将当前节点的值插入数组的首部
            if (p->left != NULL) stk.push(p->left); // 先将左子节点压入栈中
            if (p->right != NULL) stk.push(p->right); // 再将右子节点压入栈
        }
        return res;
    }

    vector<vector<int>> levelOrder(TreeNode* root) { // 层序遍历
        vector<vector<int>> res; // 存储遍历结果的二维数组
        queue<TreeNode*> q; // 实现BFS遍历的队列
        if (root != NULL) q.push(root); // 将根节点加入队列


        while (!q.empty()) { // 在队列不为空时循环
            int size = q.size(); // 当前层的节点数目
            vector<int> layer; // 存储当前层遍历结果的数组
            for (int i = 0; i < size; i++) { // 遍历当前层的所有节点
                TreeNode* p = q.front(); // 取出队头元素
                q.pop(); // 弹出队头元素
                layer.push_back(p->val); // 将当前节点值加入到当前层的数组中
                if (p->left != NULL) q.push(p->left); // 如果有左子节点，加入队尾
                if (p->right != NULL) q.push(p->right); // 如果有右子节点，加入队尾
            }
            res.push_back(layer); // 将本层的遍历结果添加至最终输出结果中
        }
        return res;
    }
};

由于这是一道比较基础的二叉树问题，因此其实现思路也相对简单。但是在实际应用中需要灵活使用各种不同的遍历方式，并且代码的实现可能会涉及到栈和队列等相关数据结构。因此，熟悉常见的算法和数据结构、灵活掌握基础知识才是写好代码的关键。

Java版本

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    public List<Integer> preorderTraversal(TreeNode root) { // 前序遍历
        List<Integer> res = new ArrayList<>(); // 存储遍历结果的数组
        Stack<TreeNode> stk = new Stack<>(); // 储存访问节点的栈
        if (root != null) stk.push(root); // 将根节点压入栈
        while (!stk.empty()) { // 在栈不为空时循环
            TreeNode p = stk.pop(); // 取栈顶元素
            res.add(p.val); // 将当前节点的值加入到数组中
            if (p.right != null) stk.push(p.right); // 先将右子节点压入栈
            if (p.left != null) stk.push(p.left); // 再将左子节点压入栈中
        }
        return res;
    }

    public List<Integer> inorderTraversal(TreeNode root) { // 中序遍历
        List<Integer> res = new ArrayList<>(); // 存储遍历结果的数组
        Stack<TreeNode> stk = new Stack<>(); // 储存访问节点的栈
        TreeNode p = root;
        while (p != null || !stk.empty()) { // 在有可访问的节点时循环
            while (p != null) { // 一直沿左子节点走到最底端
                stk.push(p);
                p = p.left;
            }
            p = stk.pop(); // 取栈顶元素
            res.add(p.val); // 将当前节点的值加入到数组中
            p = p.right; // 访问右子节点
        }
        return res;
    }

    public List<Integer> postorderTraversal(TreeNode root) { // 后序遍历
        List<Integer> res = new ArrayList<>(); // 存储遍历结果的数组
        Stack<TreeNode> stk = new Stack<>(); // 储存访问节点的栈
        if (root != null) stk.push(root); // 将根节点压入栈
        while (!stk.empty()) { // 在栈不为空时循环（前序遍历的逆序）
            TreeNode p = stk.pop(); // 取栈顶元素
            res.add(0, p.val); // 将当前节点的值插入数组的首部
            if (p.left != null) stk.push(p.left); // 先将左子节点压入栈中
            if (p.right != null) stk.push(p.right); // 再将右子节点压入栈
        }
        return res;
    }

    public List<List<Integer>> levelOrder(TreeNode root) { // 层序遍历
        List<List<Integer>> res = new ArrayList<>(); // 存储遍历结果的二维数组
        Queue<TreeNode> q = new LinkedList<>(); // 实现BFS遍历的队列
        if (root != null) q.offer(root); // 将根节点加入队列
        while (!q.isEmpty()) { // 在队列不为空时循环
            int size = q.size(); // 当前层的节点数目
            List<Integer> layer = new ArrayList<>(); // 存储当前层遍历结果的数组
            for (int i = 0; i < size; i++) { // 遍历当前层的所有节点
                TreeNode p = q.poll(); // 取出队头元素
                layer.add(p.val); // 将当前节点值加入到当前层的数组中
                if (p.left != null) q.offer(p.left); // 如果有左子节点，加入队尾
                if (p.right != null) q.offer(p.right); // 如果有右子节点，加入队尾
            }
            res.add(layer); // 将本层的遍历结果添加至最终输出结果中
        }
        return res;
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-01-20，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构与算法