[数据结构与算法] 144/94/145 二叉树的前/中/后序遍历

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 144/94/145 二叉树的前/中/后序遍历 -> 正文阅读

[数据结构与算法]144/94/145 二叉树的前/中/后序遍历

一、二叉树的三种遍历（递归版）

思路
- 确定递归函数的参数以及返回类型
- 确定递归终止条件
- 确定单层逻辑
前序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> resu;
        preorder(resu, root);
        return resu;
    }
    void preorder(vector<int>& resu, TreeNode* root){
        if(root == nullptr) return;
        resu.push_back(root->val);
        preorder(resu, root->left);
        preorder(resu, root->right);
    }
};

中序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> resu;
        inorder(resu, root);
        return resu;
    }
    void inorder(vector<int>& resu, TreeNode* root){
        if(root == nullptr) return;
        inorder(resu,root->left);
        resu.push_back(root->val);
        inorder(resu,root->right);
    }
};

后序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> resu;
        postorder(resu, root);
        return resu;
    }
    void postorder(vector<int>& resu, TreeNode* root){
        if(root == nullptr) return;
        postorder(resu,root->left);
        postorder(resu,root->right);
        resu.push_back(root->val);
    }
};

二、二叉树的三种遍历（迭代版）

前序遍历
- 中-左-右
- 将根节点入栈。将根节点出栈表示访问该节点，即输出其值，再将右孩子入栈，最后将左孩子入栈。栈有后进先出的特点，此时后进的左孩子先出栈也就先被访问。
- 不断迭代直到栈为空表示遍历完毕。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> resu;//储存结果向量
        stack<TreeNode*> stk;
        if(root==NULL) return resu;
        stk.push(root);//根节点入栈，确保此时栈非空
        while(!stk.empty()){//依次处理根节点、如果左右孩子非空，就将它们入栈
            TreeNode* tmp = stk.top();
            resu.push_back(tmp->val);
            stk.pop();
            //栈为后进先出，先序遍历要先访问左孩子，就先入栈右孩子
            if(tmp->right) stk.push(tmp->right);
            if(tmp->left) stk.push(tmp->left);
        }
        return resu;
    }
};

中序遍历
- 左-中-右
- cur指向当前访问的节点，stk.top()为当前要处理的节点
- 先寻找整棵树最左边的节点，即如果cur有左孩子，就一直向左寻找，同时将访问过的节点入栈。当cur为空时表示已经到达了尽头，此时栈顶元素为整棵树最左边的节点，将cur指向该节点。将他出栈并将数据加入到结果向量中。此时将cur指向该节点的右孩子，如果不为空则进行寻找该节点右子树的最左边的节点。
- 直到栈为空或cur为空表示遍历完毕

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> resu;
        stack<TreeNode*> stk;
        TreeNode* cur = root;
        //每次处理栈顶元素
        //cur寻找子树中最左端的节点，寻找过程中将沿途的节点入栈
        while(cur!=nullptr || !stk.empty()){
            if(cur!=nullptr){
                stk.push(cur);
                cur = cur->left;
            }else{//cur为空表示已经找到最左端的节点，此时cur的父亲节点即栈顶元素为最左端的节点
                cur = stk.top();//处理最左端的节点
                stk.pop();
                resu.push_back(cur->val);
                cur = cur->right;//处理完后寻找该节点右子树中最左端的节点
            }
        }
        return resu;
    }
};

后序遍历
- 左-右-中
- 对先序遍历算法略做修改。调换将节点左右孩子入栈时的顺序，变成中-右-左，翻转resu向量得到左-右-中

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
    	//两次翻转实现后续遍历
        vector<int> resu;
        stack<TreeNode*> stk;
        if(root == nullptr) return resu;
        stk.push(root);
        while(!stk.empty()){
            TreeNode* tmp = stk.top();
            resu.push_back(tmp->val);
            stk.pop();
            //将先序遍历的中左右改为中右左
            if(tmp->left) stk.push(tmp->left);
            if(tmp->right) stk.push(tmp->right);
        }
        reverse(resu.begin(), resu.end());//翻转整个序列得到左右中
        return resu;
    }
};

三、二叉树的三种遍历（统一迭代版）

思路
- 解决访问节点的顺序与处理节点的顺序不一致问题（中序）
- 解决方法：标记法，即将要处理的节点入栈后在其后入栈一个空指针。在后续的访问中如果当前栈顶为空指针，则处理接下来的节点，将其加入到结果向量中。
前序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> resu;
        stack<TreeNode*> stk;
        if(root != NULL) stk.push(root);
        //while循环的前期在寻找节点的处理顺序，后期在按照NULL的标记处理节点
        while(!stk.empty()){
            TreeNode* cur = stk.top();//记录此时的栈顶元素
            if(cur!=NULL){//如果栈顶元素不是NULL，则继续寻找待处理节点
                stk.pop();//弹出当前节点，对该节点它的左右孩子根据遍历顺序重新入栈
                //先序遍历顺序为中左右，入栈顺序为右左中
                if(cur->right) stk.push(cur->right);
                if(cur->left) stk.push(cur->left);
                stk.push(cur);
                stk.push(NULL);//中间节点入栈后标志位入栈
            }else{//如果为NULL则表示接下来的节点为待处理的节点
                stk.pop();
                resu.push_back(stk.top()->val);
                stk.pop();
            }
        }
        return resu;
    }
};

中序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> resu;
        stack<TreeNode*> stk;
        if(root!=NULL) stk.push(root);
        while(!stk.empty()){
            TreeNode* cur = stk.top();//记录当前栈顶节点
            if(cur!=NULL){
                stk.pop();//弹出栈顶节点，根据遍历顺序对它及左右孩子进行重新入栈
                //中序遍历为左中右，入栈顺序为右中左
                if(cur->right) stk.push(cur->right);
                stk.push(cur);
                stk.push(NULL);
                if(cur->left) stk.push(cur->left);
            }else{//处理节点
                stk.pop();
                resu.push_back(stk.top()->val);
                stk.pop();
            }
        }
        return resu;
    }
};

后序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> resu;
        stack<TreeNode*> stk;
        if(root !=NULL) stk.push(root);
        while(!stk.empty()){
            TreeNode *cur = stk.top();//记录当前栈顶节点
            if(cur!=NULL){
                stk.pop();//弹出栈顶节点，对它及其左右孩子按照遍历顺序进行重新入栈
                //后序遍历为左右中，入栈顺序为中右左
                stk.push(cur);
                stk.push(NULL);
                if(cur->right) stk.push(cur->right);
                if(cur->left) stk.push(cur->left);
            }else{//处理节点
                stk.pop();
                resu.push_back(stk.top()->val);
                stk.pop();
            }
        }
        return resu;
    }
};

四、二叉树的三种遍历（morris版）

前序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> resu;
        TreeNode *cur = root;
        TreeNode *pre;
        while(cur){
            if(cur->left){
                pre = cur->left;
                while(pre->right && pre->right!=cur){
                    pre = pre->right;
                }
                if(pre->right == NULL){
                    resu.push_back(cur->val);
                    pre->right = cur;
                    cur = cur->left;
                }else{
                    pre->right = NULL;
                    cur = cur->right;
                }
            }else{
                resu.push_back(cur->val);
                cur = cur->right;
            }
        }
        return resu;
    }
};