二叉树]leetcode144:二叉树的前序遍历(medium)"/>
[二叉树]leetcode144:二叉树的前序遍历(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> preorderTraversal(TreeNode* root) {if(root==nullptr)return {};vector<int> result;stack<TreeNode*> recond;//辅助栈用来存储结点,进行前序遍历recond.push(root);//根结点进栈while(!recond.empty()){TreeNode* top=recond.top();recond.pop();//获得栈顶元素,并将栈顶元素出栈result.push_back(top->val);if(top->right!=nullptr)recond.push(top->right);//右子树先进栈,左子树后进栈,方便先访问左子树if(top->left!=nullptr)recond.push(top->left);}return result;}//解法2:递归版vector<int> preorderTraversal_2(TreeNode* root){if(root==nullptr)return {};vector<int> result;helperPreoder(root,result);return result;}void helperPreoder(TreeNode* root,vector<int>& result){if(root==nullptr)return;result.push_back(root->val);helperPreoder(root->left,result);helperPreoder(root->right,result);}
};
更多推荐
[二叉树]leetcode144:二叉树的前序遍历(medium)
发布评论