leetcode_day14

今日内容： - 递归遍历
- 迭代遍历 - 统一迭代

三道例题：

前序遍历二叉树 中序遍历二叉树 后续遍历二叉树

递归遍历

太过简单，skip # 迭代遍历（非统一版） 使用栈模拟递归过程：

前序就是先访问当前节点值，然后压栈右左孩子

vector<int> preorderTraversal(TreeNode* root) {
    if(root == nullptr) return {};
    stack<TreeNode*> st;
    TreeNode * cur = root;
    st.push(cur);
    vector<int> ans;
    while(!st.empty()) {
        cur = st.top();
        st.pop();
        ans.push_back(cur->val);
        if(cur->right) st.push(cur->right);
        if(cur->left) st.push(cur->left);
    }
    return ans;
}

中序就是先存所有左节点，直到遇null再出栈栈顶，访问值后压栈右节点（压栈的所有节点均不为空）

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

后序比较讨巧，左右中倒序就是中右左，把前序的压栈顺序调换，最后翻转结果就行，就不贴代码了

统一迭代遍历

形式统一的迭代遍历，主要思想是压栈null来标记下一个节点需要访问，这样写出来的代码在压栈部分就可以只调换顺序实现三种遍历

个人感觉比较好理解，最好记住写法，下面以后序为例给出代码

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> ans;
    stack<TreeNode *> st;
    TreeNode * cur = root;
    if(cur != nullptr)st.push(cur);
    while(!st.empty()) {
        cur = st.top();
        if(cur != nullptr) {
            st.pop();

            st.push(cur);
            st.push(nullptr);//中

            if(cur->right) st.push(cur->right);//右

            if(cur->left) st.push(cur->left);//左
        }
        else {
            st.pop();
            cur = st.top();
            ans.push_back(cur->val);
            st.pop();
        }
    }
    return ans;
}