二叉树]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);}
};
更多推荐
[二叉树]leetcode94:二叉树的中序遍历(medium)
发布评论