力扣、【前中后序遍历】-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣、【前中后序遍历】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

二叉树的前序遍历：

原题链接：

解题思路：

终止条件：当前节点为空节点，即为终止。
返回值：无返回值，因为当前节点为空节点，所以上一层的节点为叶子节点，然后将其记录下来。
每级操作：对于当前节点，我们需要去查询当前节点的左右子树。

实现代码：

/**
 * Definition for a binary tree node.
 * 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:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        dfs(root, res);
        return res;
    }

    void dfs (TreeNode* root, vector<int> &res) {
        if (root == nullptr) {
            return;
        }

        res.push_back(root->val);
        dfs(root->left, res);
        dfs(root->right, res);
    }
};

二叉树的中序遍历：

原题链接

解题思路

换一下就行；

实现代码

```cpp
/**
 * Definition for a binary tree node.
 * 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:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        dfs(root, res);
        return res;
    }

    void dfs (TreeNode* root, vector<int> &res) {
        if (root == nullptr) {
            return;
        }

        dfs(root->left, res);
        res.push_back(root->val);
        dfs(root->right, res);
    }
};

二叉树的后序遍历：

原题链接

解题思路

同上：文章来源地址https://www.toymoban.com/news/detail-664300.html

实现代码

/**
 * Definition for a binary tree node.
 * 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:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        dfs(root, res);
        return res;
    }

    void dfs (TreeNode* root, vector<int> &res) {
        if (root == nullptr) {
            return;
        }
        
        dfs(root->left, res);
        dfs(root->right, res);
        res.push_back(root->val);
    }
};