6.1二叉树的递归遍历

6.1二叉树的递归遍历

6.1二叉树的递归遍历

文章目录

​​6.1二叉树的递归遍历​​​​一、方法论​​​​二、前序遍历完整代码​​​​三、中序遍历完整代码​​​​四、后序遍历完整代码​​​​五、题型​​

二叉树的递归遍历包括：前、后、中序遍历的递归写法。

一、方法论

递归算法三要素：

确定递归函数的参数和返回值

void traversal(TreeNode* cur, vector& vec)//当前指针和数组

确定终止条件

if (cur == NULL) return;

确定单层递归逻辑

前序遍历是中->左->右的顺序，所以单层递归的逻辑就是先取中节点的数值，在处理左子树和右子树

vec.push_back(cur->val);//中traversal(cur->left,vec);//左traversal(cur->right,vec);//右

二、前序遍历完整代码

class Solution{ public: void traversal(TreeNode* cur,vector& vec) { if(cur==NULL) return; vec.push_back(cur->val);//中 traversal(cur->left,vec);//左 traversal(cur->right,vec);//右 } vector preorderTraversal(TreeNode * root) { vector result;//result是数组 traversal(root,result); return result; }}

三、中序遍历完整代码

class Solution{ public: void traversal(TreeNode* cur,vector& vec) { if(cur==NULL) return; traversal(cur->left,vec);//左 vec.push_back(cur->val);//中 traversal(cur->right,vec);//右 } vector preorderTraversal(TreeNode * root) { vector result;//result是数组 traversal(root,result); return result; }}

四、后序遍历完整代码

class Solution{ public: void traversal(TreeNode* cur,vector& vec) { if(cur==NULL) return; traversal(cur->left,vec);//左 traversal(cur->right,vec);//右 vec.push_back(cur->val);//中 } vector preorderTraversal(TreeNode * root) { vector result;//result是数组 traversal(root,result); return result; }}

五、题型

​​144.二叉树的前序遍历​​​​145.二叉树的后序遍历​​​​94.二叉树的中序遍历​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。