二叉树的中序遍历 LeetCode热题100

题目

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

思路

递归，按左中右的顺序添加节点。

利用栈先进后出的特性模拟递归。

代码

/**递归写法* 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:vector<int>ans;void InorderTraversal(TreeNode* node){if(node==nullptr){return ;}InorderTraversal(node->left);ans.push_back(node->val);InorderTraversal(node->right);}vector<int> inorderTraversal(TreeNode* root) {ans.clear();InorderTraversal(root);return ans;}
};

/**栈优化* 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:vector<int> inorderTraversal(TreeNode* root) {vector<int>ans;ans.clear();    stack<TreeNode*>st;while(!st.empty()){st.pop();}while(root!=nullptr||!st.empty()){while(root){st.push(root);root=root->left;}root=st.top();ans.push_back(root->val);st.pop();root = root->right;}return ans;}
};