94.144.145.102.107.树的基本遍历操作

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 inOrder(TreeNode *root, vector<int> &res) {
    if (!root) return;
    if (root->left) {
        inOrder(root->left, res);
    }
    res.push_back(root->val);
    if (root->right) {
        inOrder(root->right, res);
    }
}

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


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

//94
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    inOrder(root, res);
    return res;
}

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

//145
vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    postOrder(root, res);
    return res;
}


//    3
//   / \
//  9  20
//    /  \
//   15   7
//inout : [3,9,20,null,null,15,7]
//vector<int> level_vecs = {3,9,20,-1,-1,15,7};


//levelOrderByQueue
//102
vector<vector<int>> levelOrder(TreeNode* root) {
    //迭代
    //广度优先搜索(BFS队列)
    vector<vector<int>> res;
    if (!root)
        return res;
    queue<TreeNode*> q;
    q.push(root);

    while(!q.empty()) {
        res.emplace_back();//容器尾部添加一个元素
        int len = q.size();
        for (int i = 0; i < len; i++) {
            TreeNode* node = q.front();
            res.back().push_back(node->val);
            q.pop();

            if (node->left) {
               q.push(node->left);
            }
            if (node->right) {
                q.push(node->right);
            }
        }
    }
    return res;
}

void leveOrderByQueue(TreeNode* root) {
    queue<TreeNode*> q;
    if (root != nullptr) {
        q.push(root); 
    }
    while (!q.empty()) {
        TreeNode *node = q.front();
        cout << "node: " << node->val << endl;
        if (node->left) {
            q.push(node->left);
        }
        if (node->right) {
            q.push(node->right);
        }
        q.pop();
    }
}

//107
//自底向上的层序遍历
vector<vector<int>> levelOrderBottom(TreeNode* root) {
    vector<vector<int>> res;
    if (!root)
        return res;
    queue<TreeNode*> q;
    q.push(root);

    while(!q.empty()) {
        res.emplace_back();
        int len = q.size();
        for (int i = 0; i < len; i++) {
            TreeNode* node = q.front();
            res.back().push_back(node->val);
            q.pop();

            if (node->left) {
                q.push(node->left);
            }
            if (node->right) {
                q.push(node->right);
            }
        }
    }
    reverse(res.begin(), res.end());
    return res;
}