1. 前序遍历

链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

1.1 递归

代码：

class Solution {
public:
    vector<int> v;
    vector<int> preorderTraversal(TreeNode* root) {
        if(root == nullptr)
            return {};
        v.push_back(root->val);
        preorderTraversal(root->left);
        preorderTraversal(root->right);
        return v;
    }
};

1.2 迭代

代码：

class Solution {
public:
    vector<int> v;
    vector<int> preorderTraversal(TreeNode* root) {
        if(root == nullptr)
            return {};
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty())
        {
            TreeNode* tmp = st.top();
            st.pop();
            v.push_back(tmp->val);
            if(tmp->right != nullptr)
                st.push(tmp->right);
            if(tmp->left != nullptr)
                st.push(tmp->left);
        }
        return v;
    }
};

1.3 morris前序遍历

代码：

class Solution {
public:
    vector<int> v;
    vector<int> preorderTraversal(TreeNode* root) {
        if(root == nullptr)
            return {};
        TreeNode* predecessor = nullptr;
        while(root != nullptr)
        {
            if(root->left != nullptr)
            {
                predecessor = root->left;
                while(predecessor->right != nullptr && predecessor->right != root)
                {
                    predecessor = predecessor->right;
                }
                if(predecessor->right == nullptr)
                {
                    v.push_back(root->val);
                    predecessor->right = root;
                    root = root->left;
                }
                else
                {
                    root = root->right;
                    predecessor->right = nullptr;
                }
            }
            else
            {
                v.push_back(root->val);
                root = root->right;
            }
        }
        return v;
    }
};

2.中序遍历

链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

2.1 递归

代码：

class Solution {
public:
    vector<int> v;
    vector<int> inorderTraversal(TreeNode* root) {
        if(root == nullptr)
            return {};
        inorderTraversal(root->left);
        v.push_back(root->val);
        inorderTraversal(root->right);
        return v;
    }
};

2.2 迭代

2.2.1 改变树结构

代码：

class Solution {
public:
    vector<int> v;
    vector<int> inorderTraversal(TreeNode* root) {
        if(root == nullptr)
            return {};
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty())
        {
            TreeNode* tmp = st.top();
            if(tmp->left != nullptr)
            {
                st.push(tmp->left);
                tmp->left = nullptr;
                continue;
            }
            v.push_back(tmp->val);
            st.pop();
            if(tmp->right != nullptr)
                st.push(tmp->right);
        }
        return v;
    }
};

2.2.2 不改变树结构

代码：

class Solution {
public:
    vector<int> v;
    vector<int> inorderTraversal(TreeNode* root) {
        if(root == nullptr)
            return {};
        stack<TreeNode*> st;
        while(!st.empty() || root != nullptr)
        {
            while(root != nullptr)
            {
                st.push(root);
                root = root->left;
            }
            root = st.top();
            st.pop();
            v.push_back(root->val);
            root = root->right;
        }
        return v;
    }
};

2.2.3 morris中序遍历

代码：

class Solution {
public:
    vector<int> v;
    vector<int> inorderTraversal(TreeNode* root) {
        if(root == nullptr)
            return {};
        TreeNode* predecessor = nullptr;
        while(root != nullptr)
        {
            if(root->left != nullptr)
            {
                predecessor = root->left;
                while(predecessor->right != nullptr && predecessor->right != root)
                {
                    predecessor = predecessor->right;
                }
                if(predecessor->right == nullptr)
                {
                    predecessor->right = root;
                    root = root->left;
                }
                else
                {
                    v.push_back(root->val);
                    predecessor->right = nullptr;
                    root = root->right;
                }
            }
            else
            {
                v.push_back(root->val);
                root = root->right;
            }

        }
        return v;
    }
};

3.后序遍历

链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

3.1 递归

代码：

class Solution {
public:
    vector<int> v;
    vector<int> postorderTraversal(TreeNode* root) {
        if(root == nullptr)
            return {};
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        v.push_back(root->val);
        return v;
    }
};

3.2迭代

代码：

class Solution {
public:
    vector<int> v;
    vector<int> postorderTraversal(TreeNode* root) {
        if(root == nullptr)
            return {};
        stack<TreeNode*> st;
        TreeNode* prev = nullptr;
        while(root != nullptr || !st.empty())
        {
            while(root != nullptr)
            {
                st.push(root);
                root = root->left;
            }
            root = st.top();
            if(root->right == nullptr || root->right == prev)
            {
                v.push_back(root->val);
                st.pop();
                prev = root;
                root = nullptr;
            }
            else
                root = root->right;
        }
        return v;
    }
};

3.3 morris后序遍历

代码：

class Solution {
public:
    vector<int> v;
    vector<int> postorderTraversal(TreeNode* root) {
        if(root == nullptr)
            return {};

        TreeNode* newnode = new TreeNode(-1);//新建临时节点
        newnode->left = root;
        TreeNode* p = newnode;
        while(p != nullptr)
        {
            if(p->left != nullptr)
            {
                TreeNode* predecessor = p->left;
                while(predecessor->right != nullptr && predecessor->right != p)
                    predecessor = predecessor->right;
                if(predecessor->right == nullptr)
                {
                    predecessor->right = p;
                    p = p->left;
                }
                else
                {
                    predecessor->right = nullptr;
                    _postorderTraversal(p->left);
                    p = p->right;
                }
            }
            else
                p = p->right;
        }
        delete newnode;
        newnode = nullptr;
        return v;
    }
private:
    void _postorderTraversal(TreeNode* root)
    {
        int count = 0;
        while(root != nullptr)
        {
            ++count;
            v.push_back(root->val);
            root = root->right;
        }
        reverse(v.end() - count, v.end());
    }
};

4.层序遍历

链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

4.1 递归

代码：

class Solution {
public:
    vector<vector<int>> vv;
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(root == nullptr)
            return vv;
        _levelOrder(root, 0);
        return vv;
    }
private:
    void _levelOrder(TreeNode* root, int index)
    {
        if(root == nullptr)
            return;
        if(index >= vv.size())
            vv.push_back(vector<int>());
        vv[index].push_back(root->val);
        _levelOrder(root->left, index + 1);
        _levelOrder(root->right, index + 1);
    }
};

4.2 迭代

代码：

class Solution {
public:
    vector<vector<int>> vv;
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(root == nullptr)
            return vv;
        queue<TreeNode*> _que;
        _que.push(root);
        int count = 0;
        while(!_que.empty())
        {
            int sz = _que.size();
            vv.push_back(vector<int>());
            for(int i = 0; i < sz; ++i)
            {
                TreeNode* tmp = _que.front();
                _que.pop();
                vv[count].push_back(tmp->val);
                if(tmp->left != nullptr)
                    _que.push(tmp->left);
                if(tmp->right != nullptr)
                    _que.push(tmp->right);
            }
            ++count;
        }
        return vv;
    }
};