DAY21-二叉树的遍历方式

1.了解了二叉树的基础知识，

再提一嘴：二叉树的定义也要会写：

typedef struct Node {    int data;    struct Node *left;    struct Node *right;} Node;

struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}};

那么我们如何像遍历数组或者链表一样去遍历二叉树呢？

首先，二叉树的遍历方式主要有两种：

①深度优先遍历：什么是深度优先遍历？就是先一直走到最底层，然后遇到叶子节点之后返回（这里面就涉及到递归+迭代和回溯了）   一般我们有三种深度优先遍历：前序遍历（中左右）、中序遍历（左中右）、后序遍历（左右中），当然还有其他叫法，我就按自己的理解来了。

如果使用非递归的方式就要使用栈去模拟，我感觉这个模拟的过程如何转化成代码要好好去理解，4.23号华为机考第二题就是用的这种方式，题目暂时没找到链接，大家有想法可以去看一下。

附一张图

这样应该比较好理解了。

②广度优先遍历：就是一层层的去遍历，这个应该要用队列去模拟。因为队列有先进先出的特点，把每一层的节点加入队列进行遍历。

2.递归遍历

感觉递归还是需要重点去理解一下的，一想就会，一写就废，把思路转化成代码感觉是最难的！菜就多练，说到递归：可以想一下：

①：递归终止的条件是什么？（如果是深度优先遍历的话，是不是遇到叶子节点就返回啊？）

②：递归的传入参数和返回值是什么？（如果是深度优先遍历的话，参数是不是就是节点？然后返回值就是根据你的函数要返回的数据类型）

③：递归的单层逻辑是什么？（个人感觉这个比较难去实现，你要去处理什么？就是怎么样确保每次递归都能干你想干的事情）

知道这三个以后我们开始实现一下递归遍历：

以前序遍历为例：中左右

①：递归的终止条件？if（cur == NULL）  return；  

②：传入的参数？Traversal（TreeNode *root，vector &res)

一个是根节点，一个是需要保存结果的数组

③：单层逻辑？

去保存根节点，然后再去递归左节点和右节点。

class Solution {public:void traversal(TreeNode* cur, vector& vec) { if (cur == NULL) return; vec.push_back(cur->val); // 中 traversal(cur->left, vec); // 左 traversal(cur->right, vec); // 右 }vector preorderTraversal(TreeNode* root) { vector result; traversal(root, result); return result; }};

好了，中序和后序就先不看了，递归估计手撕也不会考二叉树的，二叉树这地方模拟考的比较多！