二叉树遍历

先贴一个模板题目。
二叉树的遍历介绍三种方法：
方法一：递归：
递归是最好写的方法，因为遍历二叉树的过程天然具有递归的性质，可以直接用递归函数来模拟这一过程。递归的终止条件是此时遍历的节点为空。先遍历左子树，在遍历右子树，然后将节点的值记录即可。
递归函数代码如下：

 void postorder(TreeNode *root, vector &res) {
        if (root == nullptr) {
            return;
        }
        postorder(root->left, res);
        postorder(root->right, res);
        res.push_back(root->val);
    }

方法二：迭代：
事实上迭代与递归是等价的，都是通过维护一个栈来实现的。区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其余的实现与细节都相同。

vector postorderTraversal(TreeNode *root) {
        if (!root) return {};
        vector vec;
        stack stk;
        TreeNode *prev = nullptr;
        auto node = root;
        while (!stk.empty() || node) {
            // 1.遍历到最左子节点
            while (node) {
                stk.emplace(node);
                node = node->left;
            }
            node = stk.top(); stk.pop();
            // 2.遍历最左子节点的右子树(右子树存在 && 未访问过)
            if (node->right && node->right != prev) {
                // 重复压栈以记录当前路径分叉节点
                stk.emplace(node);
                node = node->right;      
            } else {
                // 后序：填充vec在node->left和node->right后面
                // 注意：此时node的左右子树应均已完成访问
                vec.emplace_back(node->val);
                // 避免重复访问右子树[记录当前节点便于下一步对比]
                prev = node;
                // 避免重复访问左子树[设空节点]
                node = nullptr;
            }
        }
        return vec;
    }

同时不得不提一嘴，前序遍历是中左右，倒过来就是右左中，如果在前序遍历中先访问右子树，即中右左，倒过来后就是左右中，即后序遍历。可以对比一下：
前序遍历：

    vector preorderTraversal(TreeNode* root) {
        stack st;
        vector result;
        if (root == NULL) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();                       // 中
            st.pop();
            result.push_back(node->val);
            if (node->right) st.push(node->right);           // 右（空节点不入栈）
            if (node->left) st.push(node->left);             // 左（空节点不入栈）
        }
        return result;
    }

后序遍历：

    vector inorderTraversal(TreeNode* root) {
        vector result;
        stack st;
        TreeNode* cur = root;
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) { // 指针来访问节点，访问到最底层
                st.push(cur); // 将访问的节点放进栈
                cur = cur->left;                // 左
            } else {
                cur = st.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
                st.pop();
                result.push_back(cur->val);     // 中
                cur = cur->right;               // 右
            }
        }
        return result;
    }