代码随想录算法训练营第十三天|144. 二叉树的前序遍历、145.二叉树的后序遍历、94.二叉树的中序遍历

本文主要是介绍代码随想录算法训练营第十三天|144. 二叉树的前序遍历、145.二叉树的后序遍历、94.二叉树的中序遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Leetcode144. 二叉树的前序遍历

题目链接：144. 二叉树的前序遍历

C++：

方法一：递归

/*** 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 qianbianli(TreeNode *cur, vector<int> &result){if(cur == nullptr) return;result.push_back(cur->val);qianbianli(cur->left, result);qianbianli(cur->right, result);}vector<int> preorderTraversal(TreeNode* root) {vector<int> result;qianbianli(root, result);return result;}
};

方法二：迭代法，用栈实现前序遍历

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {//迭代法前序遍历vector<int> result;stack<TreeNode*> st;st.push(root);while(!st.empty()){TreeNode* cur = st.top();st.pop();if(cur == nullptr)continue;result.push_back(cur->val);st.push(cur->right);st.push(cur->left);}return result;}
};

统一迭代： 

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;if(root != nullptr) st.push(root);while(!st.empty()){TreeNode *node = st.top();if(node != nullptr){st.pop();if(node->right) st.push(node->right);if(node->left) st.push(node->left);st.push(node);st.push(nullptr);}else{st.pop();node = st.top();st.pop();result.push_back(node->val);}}return result;}
};

Python：

递归法：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def qianbianli(self, cur, result):if cur == None:returnresult.append(cur.val)self.qianbianli(cur.left, result)self.qianbianli(cur.right, result)def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:result = []self.qianbianli(root, result)return result

迭代法：

class Solution:def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:result = []stack = [root]while stack:cur = stack.pop()if cur == None:continueresult.append(cur.val)stack.append(cur.right)stack.append(cur.left)return result

Leetcode145.二叉树的后序遍历

题目链接：145. 二叉树的后序遍历

C++：

递归法：

class Solution {
public:void houbianli(TreeNode *cur, vector<int> &result){if(cur == nullptr) return;houbianli(cur->left, result);houbianli(cur->right, result);result.push_back(cur->val);}vector<int> postorderTraversal(TreeNode* root) {vector<int> result;houbianli(root, result);return result;}
};

迭代法： 

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;st.push(root);while(!st.empty()){TreeNode *cur = st.top();st.pop();if(cur == nullptr)continue;result.push_back(cur->val);st.push(cur->left);st.push(cur->right);}reverse(result.begin(), result.end());return result;}
};

统一迭代：  

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;if(root != nullptr) st.push(root);while(!st.empty()){TreeNode *node = st.top();if(node != nullptr){st.pop();st.push(node);                          //中st.push(nullptr);if(node->right) st.push(node->right);   //右if(node->left) st.push(node->left);     //左}else{st.pop();node = st.top();st.pop();result.push_back(node->val);}}return result;}
};

Python：

递归法：

class Solution:def houbianli(self, cur, result):if cur == None:returnself.houbianli(cur.left, result)self.houbianli(cur.right, result)result.append(cur.val)def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:result = []self.houbianli(root, result)return result

迭代法：

class Solution:def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:result = []stack = [root]while stack:cur = stack.pop()if cur == None:continueresult.append(cur.val)stack.append(cur.left)stack.append(cur.right)return result[::-1]

Leetcode94.二叉树的中序遍历

题目链接：94. 二叉树的中序遍历

C++：

递归法：

class Solution {
public:void zhongbianli(TreeNode* cur, vector<int> &result){if(cur == nullptr)return;zhongbianli(cur->left, result);result.push_back(cur->val);zhongbianli(cur->right, result);}vector<int> inorderTraversal(TreeNode* root) {vector<int> result;zhongbianli(root, result);return result;}
};

迭代法：

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;TreeNode *cur = root;while(!st.empty() || cur != nullptr){if(cur != nullptr){st.push(cur);cur = cur->left;}else{cur = st.top();st.pop();result.push_back(cur->val);cur = cur->right;}}return result;}
};

统一迭代： 

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;if(root != nullptr) st.push(root);while(!st.empty()){TreeNode *node = st.top();if(node != nullptr){st.pop();if(node->right) st.push(node->right);st.push(node);st.push(nullptr);if(node->left) st.push(node->left);}else{st.pop();node = st.top();st.pop();result.push_back(node->val);}}return result;}
};

Python：

递归法：

class Solution:def zhongbianli(self, cur, result):if cur == None:returnself.zhongbianli(cur.left, result)result.append(cur.val)self.zhongbianli(cur.right, result)def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:result = []self.zhongbianli(root, result)return result

迭代法：

class Solution:def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:result = []st = []cur = rootwhile cur != None or st:if cur != None:st.append(cur)cur = cur.leftelse:cur = st.pop()result.append(cur.val)cur = cur.rightreturn result

这篇关于代码随想录算法训练营第十三天|144. 二叉树的前序遍历、145.二叉树的后序遍历、94.二叉树的中序遍历的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---