【LeetCode】一文详解二叉树的三大遍历：前序、中序和后序（python和C++实现）
【LeetCode】一文详解二叉树的三大遍历：前序、中序和后序（python和C++实现）
深度学习技术前沿公众号博主
发布于 2020-05-18 10:52:52
发布于 2020-05-18 10:52:52
文章被收录于专栏：深度学习技术前沿
本文主要包括利用递归和栈的方法实现二叉树的前序、中序、后序遍历！
144. 二叉树的前序遍历
给定一个二叉树，返回它的 前序遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [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,null,2,3]
1
\
2
/
3
输出: [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,null,2,3]
1
\
2
/
3
输出: [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本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2020-04-16，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
容器服务
腾讯云容器服务（Tencent Kubernetes Engine, TKE）基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务，覆盖 Serverless、边缘计算、分布式云等多种业务部署场景，业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者，主导开源项目Crane，全面助力客户实现资源优化、成本控制。
腾讯云开发者
