二刷代码随想录，在做二叉树的时候总结一下法则，以加深对二叉树的了解。
- 递归遍历
首先，回顾一下其余的数据结构，如数组，链表，栈和队列，比拟少的呈现递归的操作，一遍都是间接遍历循环。之所以在二叉树的体系里呈现递归，和树的数据结构的特点相干：由root节点和左右节点及节点的节点...形成。实质上是存在一个指针的一直链接。因而和数组这种地址间断的构造相比，树的节点没有方法通过顺次寻找地址来遍历。所以，递归派上了用场。假使树是一个单叉树，问题倒没有那么简单（不存在前序，后序，中序遍历），只有一直将子节点传给递归函数，操作在遍历之前或者之后。递归函数的意义能够了解为他通向最初不能在递归的中央为止。因而递归函数在代码的地位十分重要，管制着代码的逻辑。 递归遍历的举例
以前序遍历为例，前序遍历是指中左右的遍历形式，“前”是指两头节点首先遍历。class Solution {public: void traversal(TreeNode* cur, vector<int>& result) { if (cur == NULL) return ; result.push_back(cur->val); traversal(cur->left, result); traversal(cur->right, result); } vector<int> preorderTraversal(TreeNode* root) { vector<int> ans; traversal(root, ans); return ans; }};1.首先是结构递归函数，首先他是个函数，得思考传入参数，返回值。传入参数基本上必定须要树的节点传入，这样在函数外面能力通过调用递归函数，并将以后的节点的左右节点传入，实现递归的性能。
2.程序。因为是前序遍历，所以咱们须要保障先对树的两头节点进行操作，那么因为传入的root就是一个两头节点，所以须要对其先进行操作。而后再traversal(left) , traversal(right)。- 层序遍历
class Solution {public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> result; queue<TreeNode*> que; if (root) que.push(root); while (!que.empty()) { int size = que.size(); vector<int> vec; for (int i = 0; i < size; i++) { TreeNode* node = que.front(); que.pop(); vec.push_back(node->val); if (node->left) que.push(node->left); if (node->right) que.push(node->right); } result.push_back(vec); } return result; }};如何了解层序遍历和一般遍历之间的异同？在我看来，层序遍历蕴含的是前序遍历的思维。首先在思考如何实现层序遍历时，咱们须要思考的问题的是如何防止树在以后节点始终递归上来。因为如果那样的话就无奈实现一层一层的输入了。所以咱们须要结构一个容器去保护每一层的节点，这里抉择队列que。在遍历以后节点的时候把他的左右节点顺次放入队列。而后再去实现遍历一层的性能，非常的奇妙。
- 一个实例：翻转二叉树
class Solution {public: void traversal(TreeNode* cur) { if (cur == NULL) return ; TreeNode* node = cur->left; cur->left = cur->right; cur->right = node; traversal(cur->left); traversal(cur->right); } TreeNode* invertTree(TreeNode* root) { traversal(root); return root; }};能够用层序遍历也能够用前序遍历或者后续遍历。这一次总结的时候在思考应该用什么遍历程序，想到了其实后序遍历也是能够的，即能够把调用递归函数的两行放在调换的后面。