二叉树的递归遍历包括：前、后、中序遍历的递归写法。
一、方法论
递归算法三要素：
- 确定递归函数的参数和返回值
void traversal(TreeNode* cur, vector<int>& 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<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;//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;//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;//result是数组 traversal(root,result); return result; } }
