C/C++教程

二叉树遍历C++实现——深度优先

本文主要是介绍二叉树遍历C++实现——深度优先，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

前序遍历

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() :val(0), left(nullptr), right(nullptr) {};
    TreeNode(int x, TreeNode* left, TreeNode* right) :val(x), left(left), right(right) {};
};
//递归法
class Solution {
public:
    void preorder(TreeNode* root, vector<int>& res) {
        if (root == nullptr) {
            return;
        }
        res.push_back(root->val);
        preorder(root->left, res);
        preorder(root->right, res);
    }

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        preorder(root, res);
        return res;
    }
};

中序遍历

int ans1;
int ans2;
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() :val(0), left(nullptr), right(nullptr) {};
    TreeNode(int x, TreeNode* left, TreeNode* right) :val(x), left(left), right(right) {};
};
class Solution {
public:
    void inorder(TreeNode* root, vector<int>& res) {
        if (!root) {
            ans2 = max(ans2, ans1);
            return;
        }
        ans1 += 1;
        inorder(root->left, res);
        res.push_back(root->val);
        inorder(root->right,res);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        ans2 = 0;
        ans1 = 0;
        inorder(root, res);
        return res;
    }
};

后序遍历

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() :val(0), left(nullptr), right(nullptr) {};
    TreeNode(int x, TreeNode* left, TreeNode* right) :val(x), left(left), right(right) {};
};
//递归法
class Solution {
public:
    void preorder(TreeNode* root, vector<int>& res) {
        if (root == nullptr) {
            return;
        }
        
        preorder(root->left, res);
        preorder(root->right, res);
        res.push_back(root->val);
    }

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        preorder(root, res);
        return res;
    }
};
这篇关于二叉树遍历C++实现——深度优先的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航