二叉树

1 - 二叉树基础知识

1.1 - 二叉树的定义

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

1.2 - 二叉树的递归遍历

前序遍历：根 左 右

144. 二叉树的前序遍历

class Solution{
public:
    void traversal(TreeNode* root, vector<int>& vec)
    {
        if (root == NULL) return;
        vec.push_back(root->val);
        traversal(root->left, vec);
        traversal(root->right, vect);
    }


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

中序遍历：左 根 右

94. 二叉树的中序遍历

void traversal(TreeNode* root, vector<int>& vec)
{
    if (root == NULL) return;
    traversal(root->left, vec);
    vec.push_back(root->val);
    traversal(root->right, vect);
}

后序遍历：左 右 根

145. 二叉树的后序遍历

void traversal(TreeNode* root, vector<int>& vec)
{
    if (root == NULL) return;
    traversal(root->left, vec);
    traversal(root->right, vect);
       vec.push_back(root->val);
}

1.3 - 二叉树的迭代遍历

迭代法遍历（非递归遍历）需要借助栈，首先用一个题来熟悉一下栈的使用：

1047. 删除字符串中的所有相邻重复项

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。在 S 上反复执行重复项删除操作，直到无法继续删除。在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

class Solution {
public:
    string removeDuplicates(string s) {
        string stk;
        for (char ch : s)
        {
            if (!stk.empty() && stk.back() == ch)
                stk.pop_back();
            else 
                stk.push_back(ch);
        }
        return stk;
    }
};

std::string类本身就提供了类似「入栈」和「出栈」的接口，可以直接当做deque使用

前序遍历（迭代法）：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> res;
        if (root == NULL) return res;
        st.push(root);
        while(!st.empty())
        {
            TreeNode* node = st.top();
            st.pop();
            res.emplace_back(node->val);
            if (node->right) st.emplace(node->right);
            if (node->left) st.emplace(node->left); 
        }
        return res;
    }
};

中续遍历（迭代法）：

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root == NULL) return res;
        TreeNode *cur = root;
        stack<TreeNode*> st;
        while(cur != NULL || !st.empty())
        {
            if (cur != NULL)
            {
                st.emplace(cur);
                cur = cur->left;
            }
            else
            {
                cur = st.top();
                st.pop();
                res.emplace_back(cur->val);
                cur = cur->right;
            }
        }
        return res;
    }
};

后续遍历（迭代法）：

需要一个prev指针记录遍历过的节点，首先一直往左走，并将所经过节点推入栈中，当 cur == nullptr 时，走到最左边，令 cur 指向栈顶节点，也就是最左节点，并将它弹出，此时有两种情况：

• 如果此节点的右节点是空的 或者 此节点的右节点已经遍历过，则直接进行 根节点 操作，之后将此节点标记成已访问的节点 prev。
• 如果此节点的右节点不为空且没被访问过，则

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

1.4 - 二叉树的层序遍历