深度优先遍历
先往深走,遇到叶子结点再往回走,分为前序遍历,中序遍历和后序遍历。方法有递归法和迭代法。前中后序遍历,指的是中间节点的遍历顺序。
前序遍历:5 4 1 2 6 7 8 中左右
中序遍历:1 4 2 5 7 6 8 左中右
后序遍历:1 2 4 7 8 6 5 左右中
深度优先遍历可利用递归法或者迭代法实现,我们先阐述递归法。
定义二叉树结点
struct TreeNode{
int val;
TreeNode* left;//指向左孩子
TreeNode* right;//指向右孩子
TreeNode(int x):val(x),left(NULL),right(NULL){}
};
实现递归算法三步:
1、确定需要输入的参数和返回值
2、确定函数的终止条件
3、确定单次递归的逻辑。
前序遍历-递归实现
class Solution{
public:
void Traversal(TreeNode* cur, vector<int>& vec){
if(cur == NULL) return;
vec.push_back(cur->val);//中
Traversal(cur->left,vec);//左
Traversal(cur->right,vec);//右
}
vector<int> preorderTraversal(TreeNode* root){
vector<int> result;
Traversal(root,result);
return result;
}
};
中序遍历-递归实现
class Solution{
public:
void Traversal(TreeNode* cur, vector<int>& vec){
if(cur == NULL) return;
Traversal(cur->left,vec);//左
vec.push_back(cur->val);//中
Traversal(cur->right,vec);//右
}
vector<int> preorderTraversal(TreeNode* root){
vector<int> result;
Traversal(root,result);
return result;
}
};
后序遍历-递归实现
class Solution{
public:
void Traversal(TreeNode* cur, vector<int>& vec){
if(cur == NULL) return;
Traversal(cur->left,vec);//左
Traversal(cur->right,vec);//右
vec.push_back(cur->val);//中
}
vector<int> preorderTraversal(TreeNode* root){
vector<int> result;
Traversal(root,result);
return result;
}
};
标签:result,遍历,TreeNode,cur,递归,Traversal,vec,二叉树
From: https://www.cnblogs.com/perngfey-note/p/18117602