【刷题记录】关于二叉树的OJ题（下）

6.二叉树的遍历

**题目链接 144. 二叉树的前序遍历 **

题干

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例1

输入：root = [1,null,2,3]
输出：[1,2,3]

示例2

输入：root = []
输出：[]

题目分析:

这个题使用递归的方式实现是非常轻松的，这里就不过多赘述，我们主要来理解迭代的思想使用迭代的方式解决此问题

改写迭代的重要性：递归的深度越深，消耗的资源越多，这个资源是在栈上的，而对于目前的操作系统来说，栈上的空间是很小的，大概只有8M左右，所以很容易出现栈溢出的问题，即使代码是没有问题的，也不一定能运行，相对于栈来说，堆上的空间就大很多了，所以一般将递归改写成迭代。

这里如果想要用迭代的方法遍历，就需要借助数据结构的栈来实现。我们来分析一下前序遍历的过程。对于任意一颗二叉树来说，可以分为左路节点和左路节点的右子树，首先就是根节点，然后是左子树的根，然后左子树的左子树，一直走下去，直到左子树为空然后走这个子树的右子树，右子树走完之后再回到上一个根的位置，再走右子树，直到回到整棵树的根节点为止。所以这里遵循后进先出的规则，因此我们借助栈来实现迭代的改写。

代码实现：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> preorder;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while(cur || !st.empty())
        {
            //开始遍历一棵树，根节点为cur
            while(cur)//遍历左路节点并入栈
            {
                st.push(cur);
                preorder.push_back(cur->val);
                cur = cur->left;
            }
            //cur现在指向二叉树的最左节点，下一步出栈，并处理右子树
            TreeNode* top = st.top();
            st.pop();
            cur = top->right;//处理右子树
        }
        return preorder;
    }
};

**拓展1**：

94. 二叉树的中序遍历 递归解法

中序遍历与前序遍历类似，只是中序序列push_back的时候，不能先push根节点，而是在处理完左子树之后在push，所以代码示例如下

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> inorder;
        TreeNode* cur = root;
        while(cur || !st.empty())
        {
            while(cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            TreeNode* top = st.top();
            st.pop();
            inorder.push_back(top->val);//这里是在处理右子树之前push_back
            cur = top->right;
        }
        return inorder;
    }
};

拓展2：

145. 二叉树的后序遍历 递归解法

同样的大思路，但是细节的地方还是要做一些修改。后续遍历要求访问完左右子树之后再访问根节点。分析过程可知，按照此思路走对于任意的右子树，将会访问两遍，分别是在此树访问右子树前和访问右子树后，这里要判断一下是否已经访问过了，如果访问过了就直接访问根，否则就访问右子树

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> postorder;
        TreeNode* cur = root;
        TreeNode* prev = nullptr;//这里使用一个prev保存上一个访问的节点
        while(cur || !st.empty())
        {
            while(cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            TreeNode* top = st.top();
//这里对右子树是否访问过的判断方法是判断上一个访问的节点是否是右子树，也可以使用其他方法，例如stack<pair<TreeNode*, bool>>
            if(top->right == nullptr || top->right == prev)//当右子树为空或者右子树已经访问过
            {
                st.pop();
                postorder.push_back(top->val);//访问根
                prev = top;//记录上一个访问节点
            }
            else//右子树没有被访问过，迭代访问右子树
                cur = top->right;
        }
        return postorder;
    }
};

这道题还有一个比较清奇的解法，就是按照类似前序遍历的方式，但是需要先遍历右子树，即根节点->右子树->左子树的顺序遍历一遍，也就是改写一下上述前序的方法，然后最终的结果reverse一下就是后序遍历序列，这里提供一下思路，有兴趣的可以试一下