当前位置：首页 > news >正文

【Leetcode】二叉树的遍历

news 来源：原创 2024/4/29 8:20:58

二叉树的遍历

在leetcode上刷题的时候还是能感觉出来对于二叉树类型的题目掌握并不是很好，所以基于一篇高质量题解梳理一下自己的思路。

①对于树和二叉树数据结构相关知识补充
《数据结构(3)：树与二叉树(上)》
②leetcode上的题解原文
《遍历二叉树的方法合集》

中序遍历

1. 中序遍历的描述
如果二叉树为空，则不进行任何处理，否则：
①中序遍历地访问左子树
②访问根节点
③中序遍历地访问右子树

2. 访问轨迹图

在这里插入图片描述
3. 实现代码

（0）问题描述
给定一个二叉树（树节点），返回它的中序遍历（vector容器）。

Leetcode-94 二叉树的中序遍历

（1）递归实现

/**
 * 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:
    void inorder(TreeNode* node,vector<int> &b){
        if(node){
            inorder(node->left,b);
            b.push_back(node->val);
            inorder(node->right,b);
        }
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        inorder(root,res);
        return res;
    }
};

（2）迭代实现

迭代方法就是采用遍历（或者循环等）其他方法来模拟递归调用时程序运行的过程。

在进行递归调用时，系统创建了栈来存储运行状态。我们可以自行构建栈的数据结构，结合栈“先进后出”的特点，按照特定的顺序将节点压栈，再弹栈、输出即可。

对于中序遍历，每一棵子树，都要按照先左子树再根节点，最后右子树的顺序进行遍历。
用栈模拟递归的思路是——针对当前的每一棵子树，先找这棵子树的左子树的最左节点（因为该节点是当前递归的终点），在找最左节点的时候还要利用栈对路径进行记录，以便继续模拟递归进行回溯。
最左节点处理完后，回到上一层的根节点，输出根节点，再移到右子节点，按照上述相同的步骤进行处理。

/**
 * 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) {
        stack<TreeNode*> st;
    	vector<int> res;
        if(root==nullptr)
    	    return res;
        
        TreeNode *cur = root;
        while(!st.empty()||cur != nullptr){
            while(cur!=nullptr){//将左子树的最左路径全部压入
                st.push(cur);
                cur = cur->left;
            }
            TreeNode *n = st.top();
            st.pop();
            res.push_back(n->val);
            if(n->right)
                cur = n->right;
        }
		return res;
    }
};

（3）Morris方法遍历实现

Morris方法实质上是借助了线索二叉树这样的数据结构，利用二叉树中的空指针域来存储每一个结点的前驱或者后继，从而不需要花费额外的存储空间。
《知乎上讲解Morris中序遍历-流程图以及过程图》
《Morris遍历二叉树的前、中、后序遍历即代码实现》
我也是看上面两篇文章来学习Morris方法的，读者可以阅读原作者的文章进行了解~

Morris的方法其实也有一个从“改变了树原来的结构”到“不改变树的结构”的优化过程，现在给出的很多题解是直接使用不改变树的结构的方法。

以中序遍历为例，来梳理一下Morris遍历的思路与代码实现。
中序遍历建立线索树（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> inorderTraversal(TreeNode* root) {
        vector<int> res;
        TreeNode *cur = root;
        TreeNode *pre;
        while(cur != nullptr){//当前节点非空时
            if(cur->left == nullptr){//左子树为空时，访问当前节点，转向右子树
                res.push_back(cur->val);
                cur = cur->right;//每次左子树遇空回溯的时候，转向右子树实际上都是转向后继了
            }
            else{//左子树非空时
                pre = cur->left;
                while(pre->right)
                    pre = pre->right;//找到左子树的最右子节点
                pre->right =cur;//该节点的右指针指向当前节点
                TreeNode *tmp = cur;
                cur = cur->left;//移向左子树
                tmp->left = nullptr;//删除左指针，防止循环
            }
        }
        return res;
    }
};

②优化-----不改变树的结构

仍然需要建立线索指针，但是在遍历之后就会删除
因为不能改变树结构，所以当前节点会经过多次遍历
为了避免循环，在第二次遍历到cur节点时候需要强制转移到右子树

p.s.上述的这一系列过程在下图中得以体现
在这里插入图片描述

/**
 * 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> res;
        TreeNode *cur = root;
        TreeNode *pre = nullptr;
        while(cur != nullptr){//当前节点非空时
            if(cur->left == nullptr){//左子树为空时，访问当前节点，转向右子树
                res.push_back(cur->val);
                cur = cur->right;
            }
            else{//左子树非空时
                pre = cur->left;
                while(pre->right && pre->right!=cur)//新增判断条件要求是第一次访问该节点，防止循环
                    pre = pre->right;//找到左子树的最右子节点
                if(pre->right == nullptr){//循环终止条件有两个，需要判断是哪一个导致循环终止的
                    pre->right =cur;//该节点的右指针指向当前节点
                    cur = cur->left;//移向左子树
                }
                else{//第二次访问节点时
                    pre->right == nullptr;//删除指针
                    res.push_back(cur->val);
                    cur = cur->right;//强制转向右子树
                }
            }
        }
        return res;
    }
};

p.s. 看了好几篇博客，代码应该是没问题的，但是在乐扣上提交一直是栈溢出…

前序遍历

1. 先(前)序遍历的描述
如果二叉树为空，则不进行任何处理，否则：
①先访问根节点
②再先序遍历地访问左子树
③先序遍历地访问右子树

2. 访问轨迹图
在这里插入图片描述
3. 实现代码

（0）问题描述
给定一个二叉树（树节点），返回它的前序遍历（vector容器）。

Leetcode-144 二叉树的前序遍历

（1）递归实现

void PreOrder(BiTree T){
    if(T!=NULL){
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

（2）迭代实现

迭代方法就是采用遍历（或者循环等）其他方法来模拟递归调用时程序运行的过程。

在进行递归调用时，系统创建了栈来存储运行状态。我们可以自行构建栈的数据结构，结合栈“先进后出”的特点，按照特定的顺序将节点压栈，再弹栈、输出即可。

对于先序遍历，我们希望二叉树按照“根节点-左子树-右子树”的顺序进行输出，那么我们可以在输出当前根节点之后，按照先右子树，再左子树的顺序将节点压入栈。

/**
 * Definition for a binary tree node.
 * 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) {
    	stack<TreeNode*> st;
    	vector<int> res;
        if(root)
    	    st.push(root);
        else return res;//不提前进行判空会有超时错误
    	while(!st.empty()){
    		TreeNode *cur = st.top();
    		st.pop();
            if(cur)//以下三个判断都不能漏
    		    res.push_back(cur->val);
            if(cur->right)
    		    st.push(cur->right);
            if(cur->left)
    		    st.push(cur->left);
    		
		}
		return res;
    }
            
};

（3）Morris方法遍历实现

先序遍历和中序遍历用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) {
        TreeNode* cur = root;
        TreeNode* pre = nullptr;
        vector<int> res;
        
        while(cur!=nullptr){
            if(cur->left == nullptr){
                res.push_back(cur->val);
                cur = cur->right;
            }
            else{
                pre = cur->left;
                while(pre->right && pre->right != cur){
                    pre = pre->right;
                }
                if(pre->right == nullptr){
                    pre->right = cur;
                    res.push_back(cur->val);
                    cur = cur->left;
                }
                else{
                    pre->right = nullptr;
                    cur = cur->right;
                }

            }
        }
        return res;
    }
};

后序遍历

1. 后序遍历的描述
如果二叉树为空，则不进行任何处理，否则：
①先后序遍历左子树
②再后序遍历右子树
③最后访问根节点

2. 访问轨迹图

在这里插入图片描述

3. 实现代码

（0）问题描述
给定一个二叉树（树节点），返回它的后序遍历（vector容器）。

Leetcode-145 二叉树的后序遍历

（1）递归实现

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

（2）迭代实现

迭代方法就是采用遍历（或者循环等）其他方法来模拟递归调用时程序运行的过程。

在进行递归调用时，系统创建了栈来存储运行状态。我们可以自行构建栈的数据结构，结合栈“先进后出”的特点，按照特定的顺序将节点压栈，再弹栈、输出即可。

/**
 * Definition for a binary tree node.
 * 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) {
    	stack<TreeNode*> st;
    	vector<int> res;
        if(root)
    	    st.push(root);
        else return res;//不提前进行判空会有超时错误
    	while(!st.empty()){
    		TreeNode *cur = st.top();
    		st.pop();
            if(cur)//以下三个判断都不能漏
    		    res.push_back(cur->val);
            if(cur->right)
    		    st.push(cur->right);
            if(cur->left)
    		    st.push(cur->left);
    		
		}
		return res;
    }
            
};

（3）Morris方法遍历

后序遍历整体上要比中序和先序更加复杂一点，思路如下：
在这里插入图片描述

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void Reverse(TreeNode* from,TreeNode* to){//反转链表
        TreeNode* x = from;
        TreeNode* y = from->right;
        TreeNode* z;
        if(from == to)
            return ;
        x->right = NULL;
        while(x != to){
            z = y->right;//保留右部链表
            y->right = x;
            x = y;
            y = z;
        }
    }
    void printreverse(TreeNode* from,TreeNode* to,vector<int>& res){
        //反序将链表数值保存进入res之中
        Reverse(from,to);
        TreeNode* p = to;
        while(true){
            res.push_back(p->val);
            if(p == from)
                break;
            p = p->right;
        }
        reverse(to,from);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        TreeNode dump(-1);//创建辅助结点
        dump.left = root;
        TreeNode* cur = &dump;
        TreeNode* pre = NULL;

        while(cur !=NULL){
            if(cur->left == NULL)
                cur = cur->right;//左子树为空，则转向右子树
            else{
                pre = cur->left;
                while(pre->right && pre->right != cur)
                    pre = pre->right;//找到当前节点左子树的最右子节点
                if(pre->right == NULL){
                    pre->right = cur;
                    cur = cur->left;
                }
                else{
                    printreverse(cur->left,pre,res);//如果第二次访问到该节点，逆序访问当前节点到其后继的链表
                    pre->right = NULL;
                    cur = cur->right;//转向右子树
                }
            }
        }
        return res;
    }
};