[数据结构与算法]二叉树的遍历

关于树的题目首先要熟练掌握的就是这三种递归遍历方式，三种遍历方式(前序遍历、中序遍历和后序遍历)掌握后就有个大致的结题框架。

中序遍历

二叉树的前序遍历遵循的是左 --> 根 --> 右的遍历顺序，其中遍历到根节点时，一般都是需要加上你需要的操作，以二叉树的中序遍历(leetcode 94)为例。

    vector<int> vec;
    vector<int> inorderTraversal(TreeNode* root) {
        if (!root) {
            return vec;
        }
        /* 前序遍历遵循左 根 右的遍历顺序 */
        traversal(root);
        return vec;
    }

    void traversal(TreeNode* node) {
        if (!node) {
            return;
        }
        /* 前序遍历遵循左 根 右的遍历顺序 */
        traversal(node->left); /* 先遍历左子树的左节点 */
        vec.push_back(node->val); /* 把根节点的值保存到vec中 */
        traversal(node->right); /* 遍历右子树 */
    }

前序遍历

那么同样的前序遍历就是在遍历左、右子树前，先将根节点的值保存的容器中。其实我们可以把根节点保存到容器的操作看做是我们在前序遍历中要做的动作，这个动作不仅限制于把值存放至容器中，比如可以是打印节点的值等等。所以树的三种遍历完全就可以看成是一个模板。
二叉树的前序遍历顺序是根 --> 左 --> 右。

    vector<int> vec;
    vector<int> PreOrderTraversal(TreeNode* root) {
        if (!root) {
            return vec;
        }
        /* 前序遍历遵循根 左 右的遍历顺序 */
        traversal(root);
        return vec;
    }

    void traversal(TreeNode* node) {
        if (!node) {
            return;
        }
        vec.push_back(node->val);
        traversal(node->left);
        traversal(node->right);
    }

后序遍历

后序遍历的顺序是左 --> 右 --> 根。

    vector<int> vec;
    vector<int> AfterOrderTraversal(TreeNode* root) {
        if (!root) {
            return vec;
        }
        /* 前序遍历遵循根 左 右的遍历顺序 */
        traversal(root);
        return vec;
    }

    void traversal(TreeNode* node) {
        if (!node) {
            return;
        }
       
        traversal(node->left);
        traversal(node->right);
        vec.push_back(node->val);
    }