当前位置：首页 > article >正文

代码随想录二刷｜二叉树｜二叉树的递归遍历

article 2024/9/20 0:09:21

代码随想录二刷｜二叉树｜二叉树的递归遍历

递归函数三要素
前序遍历
中序遍历
后序遍历

递归函数三要素

确定递归函数的参数和返回值
确定哪些参数是递归过程中需要处理的，就在递归函数中加上这个参数，并且还要明确每次递归的返回值是什么从而确定递归函数的返回类型
确定终止条件
如果递归没有终止，操作系统的内存栈就会溢出。
确定单层递归的逻辑
确定每一层单层递归要处理的问题，在这里就是重复调用自己来实现递归的过程。

前序遍历

确定递归函数的参数和返回值
因为要打印出前序遍历节点的数值，所以参数里需要传入vector来放节点的数值，除了这一点就不需要再处理什么数据了也不需要有返回值，所以递归函数返回类型就是void，代码如下：
```
void traversal(TreeNode* val, vecot<int>& vec)
```
确定终止条件
在递归的过程中，如何算是递归结束了呢，当然是当前遍历的节点是空了，那么本层递归就要结束了，所以如果当前遍历的这个节点是空，就直接return，代码如下：
```
if (cur == NULL) return;
```
确定单层递归的逻辑
前序遍历是中左右的循序，所以在单层递归的逻辑，是要先取中节点的数值，代码如下：
```
vec.push_back(cur->val);
traversal(cur->left, val);
traversal(cur->right, val);
```

完整代码如下：

class Solution {
public:
	void travelsal(TreeNode* val, vector<int>& vec) {
		if (cur == NULL) return;
		vec.push_back(cur->val);
		travelsal(cur->left, val);
		travelsal(cur->right, val);
	}
	vecot<int> preorderTraversal(TreeNode* root) {
		vetcor<int> result;
		traversal(root, result);
		return result;
	}
};

中序遍历、后序遍历与前序遍历一样：

中序遍历

void traversal(TreeNode* val, vector<int>& vec) {
	if (cur == NULL) return;
	traversal(cur->left, val);
	vec.push_back(cur->val);
	traversal(cur->right, val);
}

后序遍历

void traversal(TreeNode* val, vector<int>& vec) {
	if (cur == NULL) return;
	traversal(cur->left, val);
	traversal(cur->right, val);
	vec.push_back(cur->val);
}