# 【LeetCode】一文详解二叉树的三大遍历：前序、中序和后序（python和C++实现）

## 144. 二叉树的前序遍历

```   1
\
2
/
3
```

#### 解题思路

###### 1.1 树的前序遍历--非递归方法（栈）
• 因为先访问根节点，所以直接将root的val放入答案（ans）容器
• 利用stack来储存root。
• 当左子树遍历完后，取出root接着遍历右子树。

C++实现：

```/**
* 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) {
std::stack<TreeNode*> stack;
vector<int> ans;
while(root != NULL || !stack.empty()) {
while(root != NULL) {
stack.push(root);
ans.push_back(root->val);
root = root->left;
}
root = stack.top();
stack.pop();
root = root->right;
}
return ans;
}
};
```

Python实现:

```# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if root is None:
return []
stack,res=[root,],[]
while stack:
root = stack.pop()
if root is not None:
res.append(root.val)
if root.right is not None:
stack.append(root.right)
if root.left is not None:
stack.append(root.left)
return res
```
###### 1.2 递归的思想

C++实现

```class Solution {
public:
vector<int> ans;
vector<int> preorderTraversal(TreeNode* root) {
if(root != NULL){
ans.push_back(root -> val);
preorderTraversal(root -> left);
preorderTraversal(root -> right);
}
return ans;
}
};
```

Python实现：

```# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
res = []
def preorder(root):
if not root:return
res.append(root.val)
preorder(root.left)
preorder(root.right)
preorder(root)
return res
```

## 94. 二叉树的中序遍历

```   1
\
2
/
3
```

#### 解题思路

###### 2.1 利用栈的思想

C++实现：

```/**
* 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> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stack;
//s.push(root);
while(root || s.size() > 0){
while(root){
stack.push(root);
root = root->left;
}
root = stack.top();
stack.pop();
res.push_back(root->val);
root = root->right;
}
return res;
}
};
```

python实现：

```# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
stack = []
while root or stack:
# 把左子树压入栈中
while root:
stack.append(root)
root = root.left
# 输出 栈顶元素
root = stack.pop()
res.append(root.val)
# 遍历右子树
root = root.right
return res
```
##### 2.2 递归的思想

C++实现：

```/**
* 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> ans;
vector<int> inorderTraversal(TreeNode* root) {
if(root != NULL){
inorderTraversal(root -> left);
ans.push_back(root -> val);
inorderTraversal(root -> right);
}
return ans;
}
};
```

Python实现：

```# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
def inorder(root):
if not root:return
inorder(root.left)
res.append(root.val)
inorder(root.right)
inorder(root)
return res
```

## 145. 二叉树的后序遍历

```   1
\
2
/
3
```

#### 解题思路

##### 3.1 利用迭代的思想（栈）

C++实现：

• 先遍历左节点直到左节点为null。
• 开始遍历右节点，若该右节点有左节点，优先遍历左节点。
• 使用rightchild来记录右节点是否已被遍历过。若是：则说明以该点为根的子树已被遍历，输出根节点。若否：就开始遍历右节点，回到第二步。
```/**
* 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> postorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> stk;
TreeNode* cur = root;
TreeNode* rightchild = NULL;
while(cur || !stk.empty()){
while(cur != NULL){
stk.push(cur);
cur = cur -> left;
}
cur = stk.top();
if(!cur -> right|| rightchild == cur -> right){
ans.push_back(cur -> val);
stk.pop();
rightchild = cur;
cur = NULL;
}
else{
rightchild = NULL;
cur = cur -> right;
}
}
return ans;
}
};```

Python实现：

• 从根节点开始依次迭代，弹出栈顶元素输出到输出列表中，然后依次压入它的所有孩子节点，按照从上到下、从左至右的顺序依次压入栈中。
• 因为深度优先搜索后序遍历的顺序是从下到上、从左至右，所以需要将输出列表逆序输出。
```# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
if root is None:
return []

stack, output = [root, ], []
while stack:
root = stack.pop()
output.append(root.val)
if root.left is not None:
stack.append(root.left)
if root.right is not None:
stack.append(root.right)

return output[::-1]

```
##### 3.2 递归的思想

C++实现：

```/**
* 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> ans;
vector<int> postorderTraversal(TreeNode* root) {
if(root != NULL){
postorderTraversal(root->left);
postorderTraversal(root->right);
ans.push_back(root -> val);
}
return ans;
}
};
```

Python实现：

```# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
res = []
def postorder(root):
if not root:
return
postorder(root.left)
postorder(root.right)
res.append(root.val)
postorder(root)
return res```

0 条评论

• ### Yann Lecun纽约大学《深度学习》2020课程笔记中文版，干货满满！

【导读】Yann Lecun在纽约大学开设的2020春季《深度学习》课程，干货满满。在课程网站上出了最新的中文版课程笔记。

• ### 8款值得学习的科研论文作图软件！

科研绘图在国外已经非常流行，且被高度重视，国内科研人员也越来越重视科研方面的绘图。

• ### CVPR 2020丨基于点云的3D物体检测新框架

本文介绍的是CVPR2020入选论文《HVNet: Hybrid Voxel Network for LiDAR Based 3D Object Detecti...

• ### leecode刷题（24）-- 翻转二叉树

二叉树问题，我们首先要想到的使用递归的方式来解决，有了这个思路，处理这道问题就很简单了：先互换根节点的左右节点，然后递归地处理左子树，再递归地处理右子树，直到所...

• ### BST & AVL 二分搜索树 & 平衡二叉树的实现原理

本文完整的实现了基本的BST，由于注重的是逻辑和原理的实现，所以没有采用泛型。注意方法的访问修饰符。

• ### 【leetcode刷题】T129-翻转二叉树

https://leetcode-cn.com/problems/invert-binary-tree/

• ### 226 Invert Binary Tree

/** * Definition for a binary tree node. * function TreeNode(val) { * thi...

• ### LeetCode 783 & 530 Distance Between BST Nodes

Given a Binary Search Tree (BST) with the root node root, return the minimum dif...