[二叉树]leetcode94：二叉树的中序遍历(medium)

二叉树]leetcode94：二叉树的中序遍历(medium)"/>

[二叉树]leetcode94：二叉树的中序遍历(medium)

题目：

题解：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public://解法1:迭代版vector<int> inorderTraversal(TreeNode* root) {if(nullptr==root) return {};vector<int> result;stack<TreeNode*> recond;while(!recond.empty()||root!=nullptr){if(root!=nullptr)//进栈顺序为根左...根左，出栈顺序为左根...左根{recond.push(root);root=root->left;}else//直至上一结点的左结点为nullptr时，将上一结点的val打印，并添加其右子树{TreeNode* top=recond.top();recond.pop();result.push_back(top->val);root=top->right;}}return result;}/*解法2:递归版*/vector<int> inorderTraversal_2(TreeNode* root){if(root==nullptr)return {};vector<int> result;helperInorder(root,result);return result;}void helperInorder(TreeNode* root,vector<int>& result){if(root==nullptr)return;/*一直递归左子树直至到达叶子节点*/helperInorder(root->left,result);/*左子树为空时，开始打印根节点*/result.push_back(root->val);/*开始递归根节点的右子树*/helperInorder(root->right,result);}
};