二叉树前序遍历，中序遍历，后序遍历以及层次遍历实现

青旅半醒 2021-10-19 03:32 365阅读 0赞

一、二叉树的层次遍历

1. 非递归实现：利用队列，存储每一层次的结点进队列，再通过出队操作完成层次遍历。

代码：

1 /**
     2  * Definition for a binary tree node.
     3  * struct TreeNode {
     4  *     int val;
     5  *     TreeNode *left;
     6  *     TreeNode *right;
     7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     8  * };
     9  */
    10 class Solution {
    11 public:
    12     vector<vector<int>> levelOrder(TreeNode* root) {
    13         vector<vector<int>> res;
    14         if(root == NULL)
    15             return res;
    16         queue<TreeNode*> q;
    17         q.push(root);
    18         while(!q.empty())
    19         {
    20             int qnum = q.size();
    21             vector<int> cur;
    22             for(int i=0; i<qnum; i++)
    23             {
    24                 TreeNode* tmp = q.front();
    25                 q.pop();
    26                 cur.push_back(tmp->val);
    27                 if(tmp->left)
    28                     q.push(tmp->left);
    29                 if(tmp->right)
    30                     q.push(tmp->right);
    31             }
    32             res.push_back(cur);
    33         }
    34         return res;
    35     }
    36 };

2. 递归实现：这里的递归用到了搜索中的bfs。递归函数中需要一个level参数，来确定当前的访问层级。若当前的层级大于等于res数组中的总大小，说明到达新层，需要添加新层。

代码：

1 /**
     2  * Definition for a binary tree node.
     3  * struct TreeNode {
     4  *     int val;
     5  *     TreeNode *left;
     6  *     TreeNode *right;
     7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     8  * };
     9  */
    10 class Solution {
    11 public:
    12     void levelOrderCore(TreeNode* cur, int level, vector<vector<int>>& res)
    13     {
    14         if(!cur)
    15             return;
    16         if(level >= res.size())
    17         {
    18             res.push_back(vector<int>{});
    19         }
    20         res[level].push_back(cur->val);
    21         levelOrderCore(cur->left, level+1, res);
    22         levelOrderCore(cur->right, level+1, res);
    23     }
    24     vector<vector<int>> levelOrder(TreeNode* root) {
    25         vector<vector<int>> res;
    26         if(root == NULL)
    27             return res;
    28         levelOrderCore(root, 0, res);
    29         return res;
    30     }
    31 };

二、前序遍历

1. 非递归实现：借用栈来完成，首先根结点入栈，接下来开始清空栈，对于当前栈顶结点，先入栈右子树，再入栈左子树，这样就可以保证总是先存储左子树，再存储右子树。

代码：

1 /**
     2  * Definition for a binary tree node.
     3  * struct TreeNode {
     4  *     int val;
     5  *     TreeNode *left;
     6  *     TreeNode *right;
     7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     8  * };
     9  */
    10 class Solution {
    11 public:
    12     vector<int> preorderTraversal(TreeNode* root) {
    13         vector<int> res;
    14         if(root == NULL)
    15             return res;
    16         stack<TreeNode*> s;
    17         s.push(root);
    18         while(!s.empty())
    19         {
    20             TreeNode* tmp = s.top();
    21             s.pop();
    22             res.push_back(tmp->val);
    23             if(tmp->right)
    24             {
    25                 s.push(tmp->right);
    26             }
    27             if(tmp->left)
    28             {
    29                 s.push(tmp->left);
    30             }
    31         }
    32         return res;
    33     }
    34 };

2. 递归实现：DFS

1 /**
     2  * Definition for a binary tree node.
     3  * struct TreeNode {
     4  *     int val;
     5  *     TreeNode *left;
     6  *     TreeNode *right;
     7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     8  * };
     9  */
    10 class Solution {
    11 public:
    12     void preorderCore(TreeNode* cur, vector<int>& res)
    13     {
    14         if(!cur)
    15             return;
    16         res.push_back(cur->val);
    17         preorderCore(cur->left, res);
    18         preorderCore(cur->right, res);
    19     }
    20     vector<int> preorderTraversal(TreeNode* root) {
    21         vector<int> res;
    22         if(root == NULL)
    23             return res;
    24         preorderCore(root, res);
    25         return res;
    26     }
    27 };

三、中序遍历

1. 非递归实现：同样利用栈来实现。首先将根结点入栈，再循环将当前结点的左指针入栈，这样保证了栈顶为最左的结点。接下来清空栈的过程中，将当前栈顶的值保存，同时判断其是否存在右子树，若存在，右子树继续之前循环左指针入栈的操作，保证了当前树的中序遍历。

代码：

1 /**
     2  * Definition for a binary tree node.
     3  * struct TreeNode {
     4  *     int val;
     5  *     TreeNode *left;
     6  *     TreeNode *right;
     7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     8  * };
     9  */
    10 class Solution {
    11 public:
    12     vector<int> inorderTraversal(TreeNode* root) {
    13         vector<int> res;
    14         if(root == NULL)
    15             return res;
    16         stack<TreeNode*> s;
    17         TreeNode* tmp = root;
    18         s.push(root);
    19         while(tmp->left)
    20         {
    21             s.push(tmp->left);
    22             tmp = tmp->left;
    23         }
    24         while(!s.empty())
    25         {
    26             TreeNode* cur = s.top();
    27             res.push_back(cur->val);
    28             s.pop();
    29             if(cur->right)
    30             {
    31                 cur = cur->right;
    32                 while(cur)
    33                 {
    34                     s.push(cur);
    35                     cur = cur->left;
    36                 }
    37             }
    38         }       
    39         return res;
    40     }
    41 };

2. 递归实现：递归的方法很简单，就是先调用当前结点左子树的中序遍历，再将当前结点加入序列，最后调用当前结点右子树的中序遍历。

代码：

1 /**
     2  * Definition for a binary tree node.
     3  * struct TreeNode {
     4  *     int val;
     5  *     TreeNode *left;
     6  *     TreeNode *right;
     7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     8  * };
     9  */
    10 class Solution {
    11 public:
    12     void inorderCore(TreeNode* cur, vector<int>& res)
    13     {
    14         if(!cur)
    15             return;
    16         inorderCore(cur->left, res);
    17         res.push_back(cur->val);
    18         inorderCore(cur->right, res);
    19     }
    20     vector<int> inorderTraversal(TreeNode* root) {
    21         vector<int> res;
    22         if(root == NULL)
    23             return res;
    24         inorderCore(root, res);
    25         return res;
    26     }
    27 };

四、后序遍历

1. 非递归实现：同样利用栈，由于后序遍历的顺序是左右根，可以利用根右左来逆序输出。根右左和前序遍历非常相近，因此只需要改部分代码即可实现。

代码：

1 /**
     2  * Definition for a binary tree node.
     3  * struct TreeNode {
     4  *     int val;
     5  *     TreeNode *left;
     6  *     TreeNode *right;
     7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     8  * };
     9  */
    10 class Solution {
    11 public:
    12     vector<int> postorderTraversal(TreeNode* root) {
    13         vector<int> res;
    14         if(root == NULL)
    15             return res;
    16         stack<TreeNode*> s;
    17         s.push(root);
    18         while(!s.empty())
    19         {
    20             TreeNode* tmp = s.top();
    21             s.pop();
    22             res.push_back(tmp->val);
    23             if(tmp->left)
    24                 s.push(tmp->left);
    25             if(tmp->right)
    26                 s.push(tmp->right);
    27         }
    28         reverse(res.begin(), res.end());
    29         return res;
    30     }
    31 };

2. 递归实现：根据之前的前序遍历和中序遍历，递归的后序版本也十分简单。先遍历左子树，再遍历右子树，最后将根结点的值保存。

代码：

1 /**
     2  * Definition for a binary tree node.
     3  * struct TreeNode {
     4  *     int val;
     5  *     TreeNode *left;
     6  *     TreeNode *right;
     7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     8  * };
     9  */
    10 class Solution {
    11 public:
    12     void postorderCore(TreeNode* cur, vector<int>& res)
    13     {
    14         if(!cur)
    15             return;
    16         postorderCore(cur->left, res);
    17         postorderCore(cur->right, res);
    18         res.push_back(cur->val);
    19     }
    20     vector<int> postorderTraversal(TreeNode* root) {
    21         vector<int> res;
    22         if(root == NULL)
    23             return res;
    24         postorderCore(root, res);
    25         return res;
    26     }
    27 };

转载于:https://www.cnblogs.com/LJ-LJ/p/11197619.html