二叉树遍历
前言
在学习或工作中，总会遇到和算法相关的问题。 而二叉树在算法中是绕不过的一个场景。 这里介绍下二叉树的相关遍历方法。
二叉树遍历
- 前序遍历 前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树。
class Solution {
public:
void addTreeNode(vector<int> &treeVector, TreeNode* root) {
if (root == NULL) {
return ;
}
// 前序遍历，优先查找根节点
treeVector.push_back(root->val);
addTreeNode(treeVector, root->left);
addTreeNode(treeVector, root->right);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> treeVector;
addTreeNode(treeVector, root);
return treeVector;
}
};- 中序遍历
中序遍历是先遍历左子树，然后访问根节点，然后遍历右子树。
tips: 通常来说，对于二叉搜索树，我们可以通过中序遍历得到一个递增的有序序列 - 后序遍历 后序遍历是先遍历左子树，然后遍历右子树，最后访问树的根节点。
- 层序遍历
层序遍历就是逐层遍历树结构。
广度优先搜索是一种广泛运用在树或图这类数据结构中，遍历或搜索的算法. 该算法从一个根节点开始，首先访问节点本身。 然后遍历它的相邻节点，其次遍历它的二级邻节点、三级邻节点，以此类推
class Solution {
public:
void helper(vector<vector<int>> &res, TreeNode* root, int leval) {
if (root == NULL) {
return;
}
if (res.size() <= leval) {
vector<int> tmp;
res.push_back(tmp);
}
res[leval].push_back(root->val);
helper(res, root->left, leval + 1);
helper(res, root->right, leval + 1);
}
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
helper(res, root, 0);
return res;
}
};本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021/4/10 下，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录