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

前置知识【算法学习笔记】二叉树理论基础——关于二叉树的基础知识递归相关知识请先自行了解递归思路写明白递归就是要搞明白1.每次要传入什么参数、返回什么参数。2.什么时候递归到头了该停止了3.每次递归要用传入的参数干什么。我们要遍历获取每一个二叉树的值所以我们一定要传入我们遍历到了二叉树的哪一个位置不然我们没法判断现在在哪个位置下一次要去哪。而我们的返回值自然也就是我们遍历到的二叉树的值。当我们遍历到了二叉树的根节点发现该节点后面没有其他节点了没法继续往下遍历的时候自然就该停止了。每次递归传入的值也就是位置我们需要用它获取当前位置的值然后还要用它来确定下一个该去遍历谁了还能不能继续遍历。具体代码前序遍历TreeNode二叉树的指针val二叉树节点的值cur当前位置ret结果数组void traversal(TreeNode* cur, vectorint 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; } } vectorint preorderTraversal(TreeNode* root) { if(root 0) { return {}; } vectorint ret; traversal(root, ret); return ret; }根据前中后序遍历的定义我们可以发现无非就是中节点记录的时间不同。所以中序和后序遍历就是把ret.push_back(cur-val);移到traversal(cur-left, ret);和traversal(cur-right, ret);后面。