/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:// // 初始化// struck TreeNode{// int val;// TreeNode *left;// TreeNode *right;// TreeNode(int x): val(x),left(nullptr),right(nullprt){}// TreeNode(int x,TreeNode *left,TreeNode *right):val(x),left(left),right(right){}// }// // 创建// TreeNode* CreateTree(){// TreeNode* root =new TreeNode(1);// root->left = new TreeNode(11);// root->right = new TreeNode(12);// root->left->left = new TreeNode(21);// root->left->right = new TreeNode(21);// }/*A/ \B C/ \ \D E F前序遍历： 根 → 左 → 右
前序遍历结果：A → B → D → E → C → F
应用场景：
复制二叉树结构
计算前缀表达式（波兰表示法）
序列化二叉树中历顺序：左子树 → 根节点 → 右子树
中序遍历结果：D → B → E → A → C → F
应用场景：
二叉搜索树（BST）的有序遍历
中缀表达式求值
按顺序打印树的内容遍历顺序：左子树 → 右子树 → 根节点
后序遍历结果：D → E → B → F → C → A
应用场景：
删除二叉树（先删除子节点再删除父节点）
计算后缀表达式（逆波兰表示法）
计算目录大小（先计算子目录大小）*/// 方法一：递归void inorder(TreeNode* node_,vector<int> &result){if(node_ == nullptr) return ;inorder(node_->left,result);cout<<"节点 " << node_->val <<endl;result.push_back(node_->val);inorder(node_->right,result);}//方法一：递归 递归的时候隐式地维护了一个栈vector<int> inorderTraversal_1(TreeNode* root) {vector<int> result;inorder(root,result);return result;}vector<int> inorderTraversal(TreeNode* root) {stack<TreeNode*> s;vector<int> result;TreeNode* curr = root;while(curr !=nullptr || !s.empty()){while(curr !=nullptr) {s.push(curr);curr=curr->left;}curr = s.top();s.pop();result.push_back(curr->val);curr=curr->right;}return result;}};