什么是 二叉树

在计算机科学中，二叉树（英语：Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒。( 维基百科 )

上图就是一棵二叉树，我们有四种遍历方式来遍历每一个节点，分别为 先序遍历 、后序遍历、 中序遍历 、层序遍历。

二叉树先序遍历

先序遍历二叉树，先访问根节点，再到左子节点，最后是右子节点，上图的访问顺序是0->1->3->4->2->5->6。

使用递归的方案来遍历：

上面动态图是整个遍历的流程

开始遍历根节点，将根节点放入容器中；

接下来访问根节点的左子节点，将子节点放入容器中；

访问1节点的左子节点，将左子节点放入容器中；

3节点没有子节点，返回到1节点访问1节点的右子节点，将右子节点放入容器中；

4节点没有子节点，返回1节点，1节点已经遍历完，再往根节点返回，对根节点的右子节点进行遍历，将根节点的右子节点放入容器中；

访问2节点的左子节点，将左子节点放入容器中；

节点5没有子节点，返回到2节点，访问2节点的右子节点，将右子节点放入容器中；

整棵二叉树的前序遍历完成。

整体的遍历顺序。

以 LeetCode-144.二叉树的前序遍历 为例子

遍历的代码如下：

 class Solution {
public:
     void  Search(TreeNode* pNode,  vector <int>& vRes) {
        if(pNode == nullptr) {
            return ;
        }
        vRes.push_back(pNode->val);//遍历当前节点
        Search(pNode->left, vRes);//遍历左子节点
        Search(pNode->right, vRes);//遍历右子节点
    }

    vector<int> preorderTraversal(TreeNode*  root ) {
        vector<int> vResult;
        vResult.clear();
        Search(root, vResult);
        return vResult;
    }
};  

接下来讲解一下如何使用迭代的方式来进行 前序遍历 的。

上图是动态流程。

需要存储结果的容器，使用栈来模拟递归的流程，红色框为遍历栈顶的元素。

将根节点0放入栈中；

开始进行对栈进行操作，栈顶元素是根节点，先访问根节点，根节点放入容器。

然后再进行对根节点子节点进行操作，因为栈的特性是后进先出，前序遍历的顺序是根节点，左子节点，最后右子节点，所以右子节点先进栈；

然后再是根节点的左子节点进栈；

栈顶1节点出栈，放入容器中；

然后将1节点的右子节点放入栈，再到左子节点进栈；

3节点出栈，放入容器，没有子节点，4节点操作一样；

2节点出栈，放入容器，再将右子节点进栈，左子节点进栈；

5节点、6节点出栈，放入容器，两个节点都没有子节点，最后栈为空时，就代表二叉树已经遍历完。

对应的实现代码如下：

 class Solution {
public:

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> vResult;
        vResult.clear();
        stack<TreeNode*> s;//使用栈来模拟递归
        s.push(root);//
        while(!s.empty()) {
            TreeNode* pNode = s.top();
            s.pop();
            if(pNode != nullptr) {
                vResult.push_back(pNode->val);//当前节点
                s.push(pNode->right);//栈是先进先出，先将右子节点放入栈
                s.push(pNode->left);//最后放入左子节点，最后放入，下次迭代先访问
            }
        }
        return vResult;
    }
};