二叉树递归遍历

// 二叉树遍历是根据节点的位置来判断
// 前序：根左右 1 2 4 5 3 6 7 
// 中序：左根右 4 2 5 1 6 3 7
// 后序：左右根 4 5 2 6 7 3 1

#include <iostream>
#include <vector>

using namespace std;

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) {}
};

void PreOrder(TreeNode* root, vector<int> &result) {
    if(root == nullptr) {
        return;
    }
    
    // 前中后序只需调整以下三个函数的顺序
    result.push_back(root->val);
    cout << root->val << " ";
    PreOrder(root->left, result);
    PreOrder(root->right, result);
    return;
}

void InOrder(TreeNode* root, vector<int> &result) {
    if(root == nullptr) {
        return;
    }
    
    // 前中后序只需调整以下三个函数的顺序
    InOrder(root->left, result);
    result.push_back(root->val);
    cout << root->val << " ";
    InOrder(root->right, result);
    return;
}

void BehOrder(TreeNode* root, vector<int> &result) {
    if(root == nullptr) {
        return;
    }
    
    // 前中后序只需调整以下三个函数的顺序
    BehOrder(root->left, result);
    BehOrder(root->right, result);
    result.push_back(root->val);
    cout << root->val << " ";
    return;
}

int main() {
    
    // 一种列表的初始化方式
    TreeNode* root = new TreeNode{1,
                                new TreeNode{2,
                                            new TreeNode{4},
                                            new TreeNode{5},
                                },
                                new TreeNode{3,
                                            new TreeNode{6},
                                            new TreeNode{7},
                                },
    };

    vector<int> result;
    PreOrder(root, result);
    cout << endl;
    InOrder(root, result);
    cout << endl;
    BehOrder(root, result);
    cout << endl;


    return 0;
}