二叉树的遍历

二叉树是一种计算机数据结构。
把一个含有若干属性的自定义数据类型称之为节点，它内部至少包含关键字数据，以及引向两个节点的线索
C 语言可以表达成

struct TreeNode;
typedef TreeNode* TreeNodePtr;
struct TreeNode {
    int val;
    TreeNodePtr *left;
    TreeNodePtr *right;
};

要点在于 TreeNode 的内部结构，包含了另外两个同类型数据的线索。
数据如此组织，可以图形化为一个二叉树
从根节点 root 沿着左右子节点可以到达任何一个子节点。在图论中，这种图形结构式典型的连通图——即图中任何两个节点之间存在至少一条路径。

概念

节点，图中每个数据项，可以看成一个节点
边，节点之间存在“连通”关系，那么这个“关系”，看成一条边。二叉树中的节点的边，是父节点到左右子节点的索引关系的抽象。
在一些问题中，“边”的真实表达有各种各样的具体情况。
例如，社交网络中的好友关系，可以抽象成图的边，每个成员是网络中的一个节点
交易网络中，任何一对产生买卖关系的市场参与者，一笔交易可以抽象为一条“边”

二叉树的模型，明确表达了每个节点最多只有两个子节点，也就是说它最多有三条边——一条是和父节点的边，另外两条是和子节点的边

二叉树的遍历。

在数据结构中，数据被组织成某种形式，无论哪种结构，它的数据都是离散有序的。
按照数学中的基数理论，数据集合是有限可数的，因而可以和自然数集合 ${{0,1,2,..., n,...}}$ 产生一一对应。
于是对于每个数据结构，定义下面的概念都是有意义的。

后继。对任何一个数据项，它在数据结构组织中的下一个
前继。对任何一个数据项，它在数据结构组织中的前一个
起点。数据结构中的第一项

有了这个模型，任何数据结构可以用抽象的接口实现迭代
编程语言中，我们看两个例子
C++ 和Python 这两种语言都实现了一种叫做迭代器的东西，迭代器的思想即这里所言，使用抽象接口表达后继和前继，迭代时，迭代器不断计算出后继，即可完成遍历。

for (auto it = dataSet.begin(); it != dataSet.end(); ++it) {
  //
}

for d in dataSet:
    # do

Python的for in 语句等价于

it = iter(dataSet)
while True:
    try:
        o = next(it)  
        # handle o
    except StopIteration:
        break

这两种语言层面的“语法糖”可以迭代任何有迭代器的数据结构，有迭代器意味着数据结构抽象了“后继”(next) 接口

二叉树的后继如何计算

二叉树的遍历方式不是唯一的，有前序遍历，中序遍历，后续遍历和层序遍历几种常见的遍历方式

前序遍历
[1,2,3,4,5,6,7,8,9,10]

void preOrderTrack(TreeNode* root, vector<int> &ans) {
      if (!root) {
          return;
     }
     ans.push_back(root->val);  //(1)
     preOrderTrack(root->left, ans); //(2)
     preOrderTrack(root->right, ans); //(3) 
}

调整(1),(2),(3)的顺序可以得到中序和后续遍历
中序遍历

     preOrderTrack(root->left, ans); //(2)
     ans.push_back(root->val);  //(1)
     preOrderTrack(root->right, ans); //(3)

后续遍历

     preOrderTrack(root->left, ans); //(2)
     preOrderTrack(root->right, ans); //(3) 
     ans.push_back(root->val);  //(1)

层序遍历是一次从左到右遍历每一层节点之后，再转到下一层，实现方式可以用一个队列将每层的节点依次入队。

二叉树

如图所示的前序遍历结果:
[12 15 8 2 3 11 4 5 20 0 6 1] ——前序遍历的第一个节点是根节点
层序遍历 —— 层序遍历第一个节点是根节点
[12 15 20 8 11 0 1 2 3 4 5 null 6]
中序遍历—— 中序遍历两端的节点分辨是最左边的叶子节点，如果是二叉搜索树，中序遍历正好是一个升序序列
[2 8 3 15 4 11 5 12 0 6 20 1]
后序遍历——后续遍历的根节点是最后个节点
[2 3,8,4,5,11,15,6,0,1,20,12]

使用数据结构完成前中后和层序遍历

层序遍历

vector<int> levelOrder(TreeNode* root) {
        if (!root) {
            return vector<int>();
        }
        std::queue<TreeNode*> q;
        q.emplace(root);
        vector<int> ans;
        while (!q.empty()) {
            int qsize = q.size();
            for (int i = 0; i < qsize; ++i) {
                TreeNode *node = q.front();
                q.pop();
                ans.push_back(node->val);
                if (node->left) {
                    q.emplace(node->left);
                }
                if (node->right) {
                    q.emplace(node->right);
                }
            }
        }
        return ans;
    }

使用一个队列依次从第一层开始，将根节点压入队列。
然后从队头取元素，每弹出一个元素，检测它的左右节点是否为空，如果非空，则将其压入队尾。

前序遍历

vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        std::stack<TreeNode*> st;
        TreeNode *current = root;
        while (!st.empty() || current != nullptr) {
            while (current) {
                st.push(current);
                res.push_back(current->val);
                current = current->left;
            }
            TreeNode *node = st.top();
            //res.push_back(node->val);
            st.pop();
            current = node->right;
        }
        return res;
    }

从上面这段代码可以看出，前序遍历的后继是节点的左节点，如果节点没有左节点，那么它的后继是右节点。
如果节点已经是叶子节点（左右节点都是空），此时它的后继是沿着它的父节点路径中靠近它最近的那个父节点的右节点。说的比较绕。
举例来说，图中节点 2 的是叶子节点，它的后继是父节点的右节点 3 ，3 也是叶子节点，它的后继需要沿着父节点向上找到一个祖先节点 15, 15 的右节点是11 因而 3 的后继是11，如果15没有右节点，需要继续上溯寻找有右节点的祖先。
通过栈序存储节点，可以用先进先出的特性保证，节点能够按顺序找到它的祖先节点。
这个算法需要一定的存储空间代价，但是计算后继只需要常数时间的均摊代价。

中序遍历

稍微调整前序遍历的代码，可以得到中序遍历的非递归版本

vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        std::stack<TreeNode*> st;
        TreeNode *current = root;
        while (!st.empty() || current != nullptr) {
            while (current) {
                st.push(current);
                // res.push_back(current->val); 此处不压入
                current = current->left;
            }
            TreeNode *node = st.top();
            res.push_back(node->val); // 一旦出栈，则压入结果中，迭代指针走向右支
            st.pop();
            current = node->right;
        }
        return res;
    }

代码修改的地方只是数据提取的位置(时机)不同，前序遍历原则是每遇到一个新节点立即提取，中序则要在确认节点的父节点数据先被提取，然后提取右节点。
遍历指针先像前序遍历那样走到最左边边界的节点上，从栈中弹出，遍历指针向右。每弹出一个节点，说明当前的节点没有左节点，因此提取当前节点压入数组中。

后续遍历

后续遍历的顺序是先提取左右子节点，再提取父节点，因而根节点一定是在最后一个位置上。
为了保证这个顺序，如何用非递归的方式得到二叉树的后续遍历？

vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        
        std::stack<TreeNode*> st;
        TreeNode *current = root;
        std::unordered_map<TreeNode*, bool> table;
        while (!st.empty() || current != nullptr) {
            while (current != nullptr) {
                st.push(current);
                current = current->left;
            }
            TreeNode* node = st.top();
            if (node->right == nullptr || table[node] == true) {
                st.pop();
                res.push_back(node->val); 
                /* 确认是一个叶子节点就弹出并且放到结果中
                否则，不弹出，走进它的右支
                但是要注意，如果该节点是第二次访问到，那么就要将它弹出来
                怎么刻画这个特性？
                可以用哈希表来记忆
                */
                current = nullptr;
                
            } else {
                table[node] = true;
                current = node->right;
            }
            
        }
        return res;
    }

后续遍历的关键是提取时机，它的入栈和出栈顺序是和中序遍历一样的，所以这部分代码和中序遍历，前序遍历没有什么本质区别；
区别在于，如果遍历到一个节点，它没有左节点也没有右节点，说明它是叶子节点，那么需要提取它放到数组中；如果它左节点还有，就继续深入遍历下去，直到没有；如果它有右节点，没有左节点，这时候就要先沿着它的右树先遍历右子树再提取该节点。因此需要一个数据结构缓存这一信息。
代码中用一个哈希表表示节点的右树是否已经遍历过：
如果没有遍历过，那么不提取当前节点，直接遍历它的右子树；
如果已经遍历过，那么将其提取出来，并从栈中弹出来。