算法笔记_面试题_4.树的遍历(前序/中序/后续遍历）

ゝ一纸荒年。 2023-02-20 04:50 12阅读 0赞

**目录**

题目

解答

递归的方法

迭代的方法-前序遍历

迭代的方法-中序遍历

迭代方法-后续遍历

最优解之一

--------------------

# 题目 #

[144. 二叉树的前序遍历][144.]

给定一个二叉树，返回它的 *前序* 遍历。

*  **深度优先搜索**（DFS）：
    
     *  在这个策略中，我们采用深度作为优先级，以便从跟开始一直到达某个确定的叶子，然后再返回根到达另一个分支。
     *  深度优先搜索策略又可以根据根节点、左孩子和右孩子的相对顺序被细分为**前序遍历，中序遍历和后序遍历**。

**示例:**

输入: [1,null,2,3]  
       1
        \
         2
        /
       3 
    
    输出: [1,2,3]

**进阶:** 递归算法很简单，你可以通过迭代算法完成吗？

# 解答 #

## 递归的方法 ##

//树的结构
    struct TreeNode 
    {
    	int val;
    	TreeNode *left;
    	TreeNode *right;
    	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    
    class Solution {
    public:
        vector<int> preorderTraversal(TreeNode* root) {
            vector<int> res;
            recurse(root, res);
            return res;
        }
        void recurse(TreeNode* root, vector<int> & res) {
            if(root == nullptr) { //返回条件
                return;
            }
            //单层逻辑
            res.push_back(root->val);  //行1
            recurse(root->left, res);  //行2
            recurse(root->right, res); //行3
        }
    };
    
    //中序遍历： 行2 行1 行3
    //后续遍历： 行2 行3 行1

时间复杂度：O(n)，n是结点个数，因为每个节点都被访问至少一次。

空间复杂度：O(n)，因为使用一个数组存储遍历结果。

递归思想使用的是系统提供的栈，进行迭代。跟如下的迭代方式一致。

## 迭代的方法-前序遍历 ##

**方法1: 一层while**

先根节点入栈, 在while循环中, 弹出栈顶元素(根), 然后先右节点入栈,再左节点入栈即可.因为在while循环中弹出的是栈顶元素, 所以,上述前序遍历是, 先右节点入栈.

class Solution {
    public:
        vector<int> preorderTraversal(TreeNode* root) {
            vector<int> res;
            if(root == nullptr) 
                return res;
            
            stack<TreeNode*> st;
            st.push(root); //注意: 先把根节点《放入栈》, 然后开始表演
            while (!st.empty()) {
                TreeNode * cur = st.top();//《取出》
                st.pop();
                res.push_back(cur->val); //行1: 根
                if(cur->right) st.push(cur->right); //行2 前序: 因为是栈,所以先右节点入栈
                if(cur->left)  st.push(cur->left);  //行3: 前序: 再左节点入栈
            }
    
            return res;
        }
    };
    
    //后续遍历:
    //  则是颠倒行2和行3, 得到 根右左 的结果, 
    //  然后颠倒res结果即可：reverse(res.begin(), res.end());

**方法2:二层while**

使用栈的方式，存储每一个“根节点”，依次出栈入栈。时间复杂度和空间复杂度都是O(n)。

vector<int> preorderTraversal(TreeNode* root)
    {
        vector<int> result;
        stack<TreeNode*> stk;
        TreeNode* tmp = root;  //使用temp临时节点作为遍历对象
        while(tmp != NULL || !stk.empty())
        {
                while (tmp !=NULL) //只要有左子节点，就一直向左访问，同时将每一级的根节点存入栈中
                {
                    result.push_back(tmp->val); //这行代码在前(相对于left right行)，前序遍历
                    stk.push(tmp);
                    tmp = tmp->left;
                }
                
                //左节点访问完成后，通过弹出每一级的根节点，开始访问其右子节点	
                tmp = stk.top();
                stk.pop();
                tmp = tmp->right;
        }
        return result;
    }

## 迭代的方法-中序遍历 ##

**方法1：**一层while

class Solution {
    public:
        vector<int> inorderTraversal(TreeNode* root) {
            vector<int> res;
            TreeNode* cur = root; //注意：定义临时节点
            stack<TreeNode*> st;
            while (cur != nullptr || !st.empty()) {
                if (cur != nullptr) {
                    st.push(cur);    //注意：这里区分：“访问节点” 和 “处理节点” 两个概念
                    cur = cur->left; //注意：一直遍历访问左节点，直到为空， 
                                     //因为左先入栈，然后在后面当左没有时，处理节点，最后右节点入栈，
                                     //所以是 左根右，实现了中序
                } else {
                    cur = st.top();
                    st.pop();
                    res.push_back(cur->val);  // 处理节点
                    cur = cur->right;   //
                }
            }
    
            return res;
        }
    };

**方法2：**两层while, 其实和上面是一样的， 只不过分成两个while实现的

vector<int> inorderTraversal(TreeNode* root) 
    {
        vector<int> res;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while (cur || st.size()) 
        {
            while(cur) 
            {
                st.push(cur);
                cur= cur->left;
            }
            cur= st.top();
            st.pop();
            res.push_back(cur->val); //这行代码在中间(相对于left right行)，中序遍历
            cur= cur->right;
        }
        return res;
    }

## 迭代方法-后续遍历 ##

将前序遍历的模型，进行修改，使其成根右左，再最后加上`reverse`进行反转，得到左右根，即使后序遍历

vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        TreeNode* tmp= root;
        while(tmp || stk.size()) {
            while(tmp) {
                stk.push(tmp);
                res.push_back(tmp->val); // 根
                tmp= tmp->right;         // 右
            }
            tmp= stk.top();
            stk.pop();
            tmp= tmp->left;              // 左
        }
        reverse(res.begin(), res.end()); // 颠倒下
        return res;
    }

## 最优解之一 ##

HERETO : 莫里斯遍历 [力扣][Link 1]

[144.]: https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
[Link 1]: https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/er-cha-shu-de-qian-xu-bian-li-by-leetcode/