Day14——二叉树的前中后序遍历（迭代&&递归）

算法训练第十四天，二叉树 冲！

---

前言

今日文案：

仰望天空时，什么都比你高，你会自卑；俯视大地时，什么都比你低，你会自负；只有放宽视野，把天空和大地尽收眼底，才能在苍穹泛土之间找到你真正的位置。无须自卑，不要自负，坚持自信。

递归真的很难用文字表述，我只能写一点我自己看得懂的内容了~

---

一、二叉树前序遍历

题目来源：

力扣

解题思路（迭代）：

所谓前序，就是中左右得遍历二叉树。

保留中值后，全部优先解析左边先，然后回头解析右边。

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
            vector<int> ans;            //创建一个存放答案的数组
        stack st;            //创建一个栈
        if(root==0)
        return ans;
        st.push(root);                //先存入头节点
        while(!st.empty())
        {
            TreeNode*node=st.top();        //弹出第一个元素来使用
            st.pop();                        
            ans.push_back(node->val);    //保存值，此时的值是中值
            if(node->right)                //保存左右值，因为栈的特点，后进先出，先解析左边
            st.push(node->right);
            if(node->left)
            st.push(node->left);
        }
        return ans;
    }
};

解题思路（递归）

class Solution {
public:
 
    void mysearch(TreeNode*cur,vector<int> &ans)
    {
        if(cur==0)
        return;
        ans.push_back(cur->val);        //先插入中值
        mysearch(cur->left,ans);        //然后解析左
        mysearch(cur->right,ans);        //解析右
    }
 
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        mysearch(root,ans);
        return ans;
    }
}

因为使用递归，三种遍历方式都差不多，只需要改变一下位置就行。

二、二叉树中序

解题思路：

先一股脑往左边差到最深，把左节点全部放进栈，然后解析栈，之后保留中值，然后放入右节点解析。

中、后序两者非常相像，只是顺序问题。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack st;
        TreeNode* cur = root;
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) { // 指针来访问节点，访问到最底层
                st.push(cur); // 将访问的节点放进栈
                cur = cur->left;                // 左
            } else {
                cur = st.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
                st.pop();
                result.push_back(cur->val);     // 中
                cur = cur->right;               // 右
            }
        }
        return result;
    }
};

---

总结

疲于奔命，二叉树的递归和迭代真的非常精妙一定要多画图理解。