Given a binary tree, return the preorder traversal of its nodes' values.
Example:
Input:[1,null,2,3]
1 \ 2 / 3 Output:[1,2,3]
Follow up: Recursive solution is trivial, could you do it iteratively?
A:
simply use a stack to push right and left, and print the current node
/** * 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> preorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> myStack; if(root) myStack.push(root); while( not myStack.empty()){ auto p = myStack.top(); myStack.pop(); res.push_back(p->val); if(p->right){ myStack.push(p->right); } if(p->left){ myStack.push(p->left); } } return res; } };
Mistakes:
1: 要注意, 先往stack里加右子树,再加左子树。
2: 这次忘了先check root == nullptr
No comments:
Post a Comment