二叉树的中序遍历- 递归和栈

 

 

 

/*** 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;}};