大连手机自适应网站建设报价十大场景营销案例
题目
给定一个二叉树的根节点 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;}
};