二刷代码随想录，在做二叉树的时候总结一下规律，以加深对二叉树的理解。
- 递归遍历
首先，回顾一下其他的数据结构，如数组，链表，栈和队列，比较少的出现递归的操作，一遍都是直接遍历循环。之所以在二叉树的体系里出现递归，和树的数据结构的特点相关：由root节点和左右节点及节点的节点...构成。本质上是存在一个指针的不断链接。因此和数组这种地址连续的结构相比，树的节点没有办法通过依次寻找地址来遍历。所以，递归派上了用场。倘若树是一个单叉树，问题倒没有那么复杂（不存在前序，后序，中序遍历），只要不断将子节点传给递归函数，操作在遍历之前或者之后。递归函数的意义可以理解为他通向最后不能在递归的地方为止。因此递归函数在代码的位置非常重要，控制着代码的逻辑。 - 递归遍历的举例
以前序遍历为例，前序遍历是指中左右的遍历方式，“前”是指中间节点首先遍历。
class Solution { public: void traversal(TreeNode* cur, vector& result) { if (cur == NULL) return ; result.push_back(cur->val); traversal(cur->left, result); traversal(cur->right, result); }vector preorderTraversal(TreeNode* root) { vector ans; traversal(root, ans); return ans; } };
1.首先是构造递归函数，首先他是个函数，得考虑传入参数，返回值。传入参数基本上肯定需要树的节点传入，这样在函数里面才能通过调用递归函数，并将当前的节点的左右节点传入，实现递归的功能。
2.顺序。因为是前序遍历，所以我们需要保证先对树的中间节点进行操作，那么由于传入的root就是一个中间节点，所以需要对其先进行操作。然后再traversal(left) , traversal(right)。
- 层序遍历
class Solution {
public:
vector> levelOrder(TreeNode* root) {
vector> result;
queue que;
if (root) que.push(root);
while (!que.empty()) {
int size = que.size();
vector 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;
}
};
【[算法数据结构] 二叉树的几种操作方法及思考】可以用层序遍历也可以用前序遍历或者后续遍历。这一次总结的时候在思考应该用什么遍历顺序，想到了其实后序遍历也是可以的，即可以把调用递归函数的两行放在调换的前面。
