144. Binary Tree Preorder Traversal

Problem Statement

Given a binary tree, return the preorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

solution one:

This question is for preorder, the order of preorder is root, left, and right.

Traverse:

This version is pretty simple to understand, we defined a vector, which store the preorder of tree nodes.

Stop/Return condition: if current node is NULL, we return.

Otherwise: we put current node into the vector, and recursively do the same operation for its left tree and right tree.

And then, return.

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     void preorderTraverse(TreeNode *node, vector<int>& preorder){
13         if(node == NULL){
14             return;
15         }
16         
17         preorder.push_back(node->val);
18         preorderTraverse(node->left, preorder);
19         preorderTraverse(node->right, preorder);
20         return;
21     }
22     
23     vector<int> preorderTraversal(TreeNode* root) {
24         vector<int> preorder;
25         preorderTraverse(root, preorder);
26         return preorder;       
27     }
28 };

Divide and conquer:

Normally, divide and conquer will split the problem into subsets, and deal the subsets individually.

In this question, for each node, we test if it is NULL first, return if it is.

Otherwise (node is not NULL), we get its left and right subsets.

And process left and right according to what we want.

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     // this version is divide && conquer
13     vector<int> preorderTraversal(TreeNode* root) {
14         vector<int> preorder;
15         if(root == NULL){
16             return preorder;
17         }
18         // divide
19         vector<int> left = preorderTraversal(root->left);
20         vector<int> right = preorderTraversal(root->right);
21         // conquer
22         preorder.push_back(root->val);
23         preorder.insert(preorder.end(), left.begin(), left.end());
24         preorder.insert(preorder.end(), right.begin(), right.end());
25         return preorder;
26     }
27 };

Non-traverse version:

For tree traverse, there are three different ordrs:

preorder: root, left, right

Inorder: left, root, right

postorder: left, right, root

For non-traverse version, we use stack to store the tree node we already traversed.

Pop the top element from stack if current node is NULL, and push the right son of the node into stack again.

Until, the stack is empty.

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     vector<int> preorderTraversal(TreeNode* root) {
13         // this is the non traverse version
14         vector<int> preorder;
15         if(root == NULL){
16             return preorder;
17         }
18         stack<TreeNode*> node_stack;
19         TreeNode* cur_node = root;
20         node_stack.push(cur_node);
21         while(!node_stack.empty()){
22             if(cur_node){
23                 node_stack.push(cur_node);
24                 preorder.push_back(cur_node->val);
25                 cur_node = cur_node->left;    
26             } else {
27                 cur_node = node_stack.top();
28                 node_stack.pop();
29                 cur_node = cur_node->right;
30             }
31         }
32         return preorder;
33     }
34 };