【算法学习笔记】二叉树的前中后序遍历——递归的简单应用

前置知识

【算法学习笔记】二叉树理论基础——关于二叉树的基础知识

递归相关知识请先自行了解

递归思路

写明白递归就是要搞明白1.每次要传入什么参数、返回什么参数。2.什么时候递归到头了该停止了3.每次递归要用传入的参数干什么。

我们要遍历获取每一个二叉树的值，所以我们一定要传入我们遍历到了二叉树的哪一个位置，不然我们没法判断现在在哪个位置，下一次要去哪。而我们的返回值自然也就是我们遍历到的二叉树的值。

当我们遍历到了二叉树的根节点，发现该节点后面没有其他节点了，没法继续往下遍历的时候，自然就该停止了。

每次递归传入的值也就是位置，我们需要用它获取当前位置的值，然后还要用它来确定下一个该去遍历谁了，还能不能继续遍历。

具体代码

前序遍历

TreeNode：二叉树的指针

val：二叉树节点的值

cur：当前位置

ret：结果数组

void traversal(TreeNode* cur, vector<int> &ret)
{
ret.push_back(cur->val);

if(cur->left != 0)
{
traversal(cur->left, ret);
}
if(cur->right != 0)
{
traversal(cur->right, ret);
}

if(cur->left == 0 && cur->right == 0)
{
return;
}
}
vector<int> preorderTraversal(TreeNode* root) {
if(root == 0)
{
return {};
}
vector<int> ret;
traversal(root, ret);
return ret;
}

根据前中后序遍历的定义，我们可以发现无非就是中节点记录的时间不同。所以中序和后序遍历就是把ret.push_back(cur->val);移到traversal(cur->left, ret);和traversal(cur->right, ret);后面。