1、树的结构

根据leetcode中常用的结构，我们声明一棵树通常包括

struct Node{
    int val;
    Node *left,*right;
    Node(int v){
        val=v;
        left=nullptr;
        right=nullptr;
    }
};

2、树的先序遍历

先将遍历到的root进栈，然后判断栈顶元素是否有右子树

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if(!root) return res;
        stack<TreeNode*> stk;
        while(root || stk.size()){
            while(root){
                stk.push(root);
                res.push_back(root->val);
                root=root->left;
            }
            auto t=stk.top();
            stk.pop();
            if(t->right) root=t->right;
        }
        return res;
    }
};

3、树的中序遍历

元素进栈时间变成了我们遍历完左子树后的时间

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> stk;
    while(root||stk.size()){
        while(root){
            stk.push(root);
            root=root->left;
        }
        auto t=stk.top();
        stk.pop();
        res.push_back(t->val);
        if(t->right) root=t->right;
    }
    return res;
}

4、树的后序遍历

这里我们的后序遍历是借用先序遍历的思路来完成的
先序遍历：根、左、右
后序遍历：左、右、根
因此我们转化先序遍历的顺序，让其变为根、右、左，最后颠倒一下编程左、右、根即可

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if(!root) return res;
        stack<TreeNode*> stk;
        while(root || stk.size()){
            while(root){
                stk.push(root);
                res.push_back(root->val);
                root=root->right;
            }
            auto t=stk.top();
            stk.pop();
            if(t->left) root=t->left;
        }
        reverse(res.begin(),res.end());
        return res;
    }
};

5、树的层序遍历

leetcode中层序遍历需要我们按层输出元素，因此我们每一次进入一层以后统计一下元素个数，然后进行操作即可

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if(!root) return res;
    queue<TreeNode*> q;
    q.push(root);
    while(q.size()){
        int sum=q.size();
        vector<int> path;
        for(int i=0;i<sum;i++){
            auto t=q.front();
            q.pop();
            path.push_back(t->val);
            if(t->left) q.push(t->left);
            if(t->right) q.push(t->right);
        }
        res.push_back(path);
    }
    return res;
}

6、由给定带有叶子节点的序列还原树

对应leetcode的树的序列化和反序列化

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

string s;

void dfs_s(TreeNode* root){
    if(!root){
        s+="#,";
        return;
    }else{
        int t=root->val;
        s+=to_string(t)+",";
        dfs_s(root->left);
        dfs_s(root->right);
    }
}

// 序列化：将树变成字符串
string serialize(TreeNode* root) {
    dfs_s(root);
    return s;
}

// 这里注意，我们所有dfs_d公用一个u，这里u传入的是引用
TreeNode* dfs_d(string &data,int &u){
    if(data[u]=='#'){
        //跳过当前符号和逗号
        u+=2;
        return NULL;
    }else{
        int k=u;
        while(data[u]!=',') u++;
        string temp=data.substr(k,u-k);
        //跳过逗号
        u++;
        TreeNode* root=new TreeNode(stoi(temp));
        root->left=dfs_d(data,u);
        root->right=dfs_d(data,u);
        return root;
    }
}

// 反序列化，将字符串恢复成树
TreeNode* deserialize(string data) {
    int u=0;
    return dfs_d(data,u);
}