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

时间：2019-07-16 21:42:20 阅读：68 评论：0 收藏：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

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)