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

目录

题目

解答

递归的方法

迭代的方法-前序遍历

迭代的方法-中序遍历

迭代的方法-后序遍历

最优解之一

题目

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 preorderTraversal(TreeNode* root) {
        vector res;
        recurse(root, res);
        return res;
    }
    void recurse(TreeNode* root, vector & 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 preorderTraversal(TreeNode* root) {
        vector res;
        if(root == nullptr) 
            return res;
        
        stack 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 preorderTraversal(TreeNode* root)
{
    vector result;
    stack 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 inorderTraversal(TreeNode* root) {
        vector res;
        TreeNode* cur = root; //注意：定义临时节点
        stack 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 inorderTraversal(TreeNode* root) 
{
    vector res;
    stack 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 postorderTraversal(TreeNode* root) {
    vector res;
    stack 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 : 莫里斯遍历 力扣