Recursive solution:
Time: O(n) -- n number of nodes
Space: O(L) -- tree height
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | /** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { public: /** * @param root: The root of binary tree. * @return: Preorder in vector which contains node values. */ vector<int> preorderTraversal(TreeNode *root) { // write your code here vector<int> result; preorder(root, result); return result; } void preorder(TreeNode* node, vector<int>& v){ if(!node) return; v.push_back(node->val); if(node->left) preorder(node->left, v); if(node->right) preorder(node->right, v); } }; |
Iterative solution:
Use stack to record nodes, remember push the right child first then left child ---- make sure pop in post order
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | /** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { public: /** * @param root: The root of binary tree. * @return: Preorder in vector which contains node values. */ vector<int> preorderTraversal(TreeNode *root) { vector<int> result; if(!root) return result; stack<TreeNode*> s; s.push(root); while(!s.empty()){ TreeNode *cur = s.top(); s.pop(); result.push_back(cur->val); if(cur->right) s.push(cur->right); if(cur->left) s.push(cur->left); } return result; } }; |
没有评论:
发表评论