前言
提示：这里可以添加本文要记录的大概内容：
例如：随着人工智能的不断发展，机器学习这门技术也越来越重要，很多人都开启了学习机器学习，本文就介绍了机器学习的基础内容。
提示：以下是本篇文章正文内容，下面案例可供参考
一、对称的二叉树
思路：递归法
- 1.题目的意思就是判断这棵树是否是轴对称的，所以我们需要将这棵树分成左子树和右子树两部分。
- 2.给一个
left，right指针分别指向左子树和右子树的根。随后判断这两棵树是否是轴对称。 - 轴对称要点：
- （1）左右子树的val值是否相等。
- （2）左子树的左子节点和右子树的右子节点的val值是否相等。
- （3）左子树的右子节点和右子树的左子节点的val值是否相等。
- 所以第二第三点递归判断即可。
- 注意：递归结束的条件是如果其中一个节点为空，或者都为空，返回。
具体代码如下：
//思路：判断左右子树是否对称， class Solution { public: bool isSameTree(TreeNode* left,TreeNode* right) { //情况1：其中一个节点为空，返回false；或者两个都为空，返回true if(left == nullptr || right == nullptr) return left == right; //都不为空，先判断左右节点val值是否相等，再递归左右子树 return left->val == right->val && isSameTree(left->left,right->right) && isSameTree(left->right,right->left); } bool isSymmetric(TreeNode* root) { if(root == nullptr) return true; TreeNode* left = root->left; TreeNode* right = root->right; return isSameTree(left,right); } };
时间复杂度：O（n），最坏空间复杂度O（n），当二叉树退化为链式结构时；最好空间复杂度O（logN）,当二叉树为满二叉树时
二、二叉树的所有路径
思路：递归法
- 给一个顺序表
path存储二叉树的所有路径，给一个字符串string road代表每一条路，当该条路到达路的尽头，也就是遇到叶子节点时，将road存储到path中。 - 具体如下：
- （1）从根节点开始遍历整棵树，如果该节点为空，则不用做什么，返回即可。
- （2）如果该节点的左右子节点均为空，表明获得了一条路径，将该路径
road存储到path中，再返回即可。 - （3）如果不是以上两种情况，则继续往下遍历即可，可以先遍历左子树，再遍历右子树，或者相反均可。
- 注意：每次调用栈桢，road在每一层栈桢中都是不相同的，而一旦更新path，在其他每层栈桢中都会同时更新。
图解如下：
具体代码如下：
class Solution { public: void PrevOrder(TreeNode* root,string road, vector<string>& path) { //只要该节点不为空，则可继续走 if(root!=nullptr) { road+=to_string(root->val); //只要左右节点都为空，表明获得一条路径 if(root->left == nullptr && root->right == nullptr) { path.push_back(road); } //如果不是以上的情况，则可以继续递归 else { node+="->"; PrevOrder(root->left,road,path); PrevOrder(root->right,road,path); } } return ; } vector<string> binaryTreePaths(TreeNode* root) { string node = ""; vector<string> path; PrevOrder(root,road,path); return path; } };
时间复杂度O（n^2），每次递归需要对road进行拷贝构造，时间代价为O(n)，递归n个节点，为O(n^2);空间复杂度O（n^2），每次调用栈桢进行road的拷贝，消耗N^2的空间；
总结
通过这次算法，我深知自己的递归理解得不够透彻，所以需要继续练习递归二叉树方面的题型，说实话，理解递归还是比较重要的。
