Return the preorder traversal of a binary tree’s nodes’ values. The pre-order displays the root/current node’s value first, then recursively calling into its left sub tree and right sub tree respectively.
Recursion
Based on the definition of the pre-order, it is trivial to write a recursion:
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 | /** * 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: void preorderTraversal(TreeNode* root, vector<int> &r) { if (root == NULL) { return; } r.push_back(root->val); preorderTraversal(root->left, r); preorderTraversal(root->right, r); } vector<int> preorderTraversal(TreeNode* root) { vector<int> r; preorderTraversal(root, r); return r; } }; |
/** * 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: void preorderTraversal(TreeNode* root, vector<int> &r) { if (root == NULL) { return; } r.push_back(root->val); preorderTraversal(root->left, r); preorderTraversal(root->right, r); } vector<int> preorderTraversal(TreeNode* root) { vector<int> r; preorderTraversal(root, r); return r; } };
Without helper function, you can do it straightforward by appending vector to the vector:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> r; if (root == NULL) { return r; } vector<int> x; r.push_back(root->val); if (root->left != NULL) { x = preorderTraversal(root->left); r.insert(r.end(), x.begin(), x.end()); } if (root->right != NULL) { x = preorderTraversal(root->right); r.insert(r.end(), x.begin(), x.end()); } return r; } }; |
class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> r; if (root == NULL) { return r; } vector<int> x; r.push_back(root->val); if (root->left != NULL) { x = preorderTraversal(root->left); r.insert(r.end(), x.begin(), x.end()); } if (root->right != NULL) { x = preorderTraversal(root->right); r.insert(r.end(), x.begin(), x.end()); } return r; } };
Please note that it is easy by rearranging the order of r.push_back(root->val); in order to do post-order, in-order traversal.
Using Stack
The iterative approach would be using a stack (First In First Out), so we push the right sub tree first as they are handled later.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> r; stack<TreeNode*> st; if (root) { st.push(root); } while (!st.empty()) { auto p = st.top(); st.pop(); r.push_back(p->val); if (p->right) { st.push(p->right); } if (p->left) { st.push(p->left); } } return r; } }; |
class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> r; stack<TreeNode*> st; if (root) { st.push(root); } while (!st.empty()) { auto p = st.top(); st.pop(); r.push_back(p->val); if (p->right) { st.push(p->right); } if (p->left) { st.push(p->left); } } return r; } };
This is the case that using stack to emulate the recursion.
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
421 wordsloading...
Last Post: How to Reverse Linked List within Interval? (C/C++)
Next Post: C++ Coding Exercise - Binary Tree Postorder Traversal