算法力扣刷题三十五【二叉树基础和递归遍历】

前言

进入二叉树学习。
继续。

一、二叉树基础理论

理论篇——参考链接

以下是大纲：

二、遍历方式

学习递归法实现前、中、后遍历方法。

“输入”阶段

此处用了第一次递归法实现根据题目的双指针操作，传递递归的参数。

解释递归

（1）递归：自己调用自己。重复执行一段代码，但是和循环有区别。
（2）过程：先传递，不到终止条件，继续传递；还不到终止条件，继续传递；……if判断到终止条件，开始return；返回上一层，从调用之后继续执行，结束后；再返回上一层，从调用自己之后继续执行，结束后；继续往上，直到第一层。
在这里插入图片描述

如何写好递归？

（1）前序遍历：

确定递归函数的参数和返回值：
- 参数需要时可以再补充。一般需要传入root根节点和数组用来存放结果。
- 返回值一般void。
确定终止条件：
- if(cur == NULL) ，返回。
确定单层递归的逻辑：

（2）中序和后序同理。

“输出”阶段

前序遍历题目：【144.二叉树的前序遍历】

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:void traversal(TreeNode* cur, vector<int>& record){//终止条件if(cur == nullptr){return;}record.push_back(cur->val);//把根节点放入；traversal(cur->left,record);traversal(cur->right,record);}vector<int> preorderTraversal(TreeNode* root) {vector<int> result;traversal(root,result); //返回到这一层，说明result已经放好结果。return result;}
};

中序遍历题目：【94.二叉树的中序遍历】

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:void traversal(TreeNode* cur,vector<int>& record){if(cur == nullptr){return;}traversal(cur->left,record);//先左子树record.push_back(cur->val);//再根节点traversal(cur->right,record);//再右子树}vector<int> inorderTraversal(TreeNode* root) {vector<int> result;traversal(root,result);return result;}
};

后序遍历题目：【145.二叉树的后序遍历】

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:void traversal(TreeNode* cur,vector<int>& record){if(cur == nullptr){return;}traversal(cur->left,record);    //先左子树traversal(cur->right,record);   //再右子树record.push_back(cur->val);     //再放入根节点}vector<int> postorderTraversal(TreeNode* root) {vector<int> result;traversal(root,result);return result;}
};