二叉树的遍历（深度优先搜索）

二叉树的遍历方式有两种：深度优先搜索（采用递归方式实现），广度优先搜索。

深度优先搜索中包括三种遍历方式：前序遍历，中序遍历，后序遍历。

 前序遍历：

遍历中间节点，再遍历左节点，最后遍历右节点。

如下图，先遍历中间节点（5），再遍历左节点（4），4不仅是5的左节点还是2和1的中间节点，所以向下遍历就是4的左节点（2），右节点（1），最后再是最中间节点（5）的右节点（6）。

在进行任何一种遍历时一定要保证遍历到底！

递归实现代码：

从根节点开始遍历，如果节点不为空，就将节点的数值存入到数组中，这时存入的是现在的中间节点，通过递归的方式将遍历左节点到底，到底后再向下指针为空，又返回到调用它的上一层递归（底的中间节点）。 

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

中序遍历：

遍历左节点，再遍历中节点，最后遍历右节点。

与前序遍历相似，只是改变了顺序，不直接输出中间界定，而是将左节点遍历到底。

        traversal(cur->left,vec);vec.push_back(cur->val);traversal(cur->right,vec);

后序遍历：

遍历左节点，再遍历右节点，最后遍历中间节点。

        traversal(cur->left,vec);traversal(cur->right,vec);vec.push_back(cur->val);

Constant dripping wears away a stone.