二叉数的统一迭代法
序列的判断顺序
前序排列
顺序判断：先将根节点入栈 ，然后每次从栈顶取出节点（根节点），处理其值，接着按照先右子节点后左子节点入栈。因为栈是后进先出，所以先处理根节点，再处理左子树（左子树在栈顶后出栈 ），最后处理右子树，顺序是中左右。
中序遍历
顺序判断：使用一个指针 cur 从根节点开始，先不断将当前节点及其左子树节点压入栈， 直到左子树为空，此时从栈中弹出节点（左节点处理完了，处理中间节点 ），处理其值，然后让 cur 指向该节点的右子节点，继续上述过程。整体顺序是左中右。
后续排列
顺序判断：和前序遍历类似，先将根节点入栈，每次从栈顶取出节点，处理其值，不过是先将左子节点入栈，再将右子节点入栈。最后将结果数组反转，得到的顺序就是左右中 。 因为栈的特性，先入栈的后处理，经过反转操作后就符合后序遍历左右中（即左子树 - 右子树 - 根节点 ）的顺序了。
144. 二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
解释：
示例 2：
输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[1,2,4,5,6,7,3,8,9]
解释：
示例 3：
输入：root = []
输出：[]
示例 4：
输入：root = [1]
输出：[1]
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int>result;stack<TreeNode*>st;if(root!=NULL) st.push(root);while(!st.empty()){TreeNode*node= st.top();if(node!=NULL){st.pop();if(node->right) st.push(node->right);if(node->left) st.push(node->left);st.push(node);st.push(NULL); } else{st.pop();node=st.top();st.pop();result.push_back(node->val);}}return result;}
};145. 二叉树的后序遍历
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[3,2,1]
解释：
示例 2：
输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[4,6,7,5,2,9,8,3,1]
解释：
示例 3：
输入：root = []
输出：[]
示例 4：
输入：root = [1]
输出：[1]
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int>result;stack<TreeNode*>st;if(root!=NULL) st.push(root);while(!st.empty()){TreeNode*node= st.top();if(node!=NULL){st.pop();st.push(node);st.push(NULL); if(node->right) st.push(node->right);if(node->left) st.push(node->left);} else{st.pop();node=st.top();st.pop();result.push_back(node->val);}}return result;}
};94. 二叉树的中序遍历
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[3,2,1]
解释：
示例 2：
输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[4,6,7,5,2,9,8,3,1]
解释：
示例 3：
输入：root = []
输出：[]
示例 4：
输入：root = [1]
输出：[1]
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int>result;stack<TreeNode*>st;if(root!=NULL) st.push(root);while(!st.empty()){TreeNode*node= st.top();if(node!=NULL){st.pop();if(node->right) st.push(node->right);st.push(node);st.push(NULL); if(node->left) st.push(node->left);} else{st.pop();node=st.top();st.pop();result.push_back(node->val);}}return result;}
};