Binary tree Traversals

recursive很容易写binary tree iterative后来再补上：DFS vs BFS是最好的queue vs stack 实例

1, Depth first traversals: inorder (left, root, right) preorder (root, left, right) postorder (left, right, root) The root postion decides the order. For example： Inorder:

void helper(TreeNode* root, vector<int>&res) { if(root == NULL) return; helper(root->left, res); res.push_back(root->val); helper(root->right, res); }

Preorder:

void helper(TreeNode* root, vector<int>&res) { if(root == NULL) return; res.push_back(root->val); helper(root->left, res); helper(root->right, res); }

PostOrder:

void helper(TreeNode* root, vector<int>&res) { if(root == NULL) return; helper(root->left, res); helper(root->right, res); res.push_back(root->val); }

2, Breadth first traversal: Level order:

/** * 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: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>>res; if(root == NULL) return res; queue<TreeNode*>q; q.push(root); while(!q.empty()) { vector<int>row; int size = q.size(); for(int i = 0; i < size; i++) { TreeNode* cur = q.front(); q.pop(); row.push_back(cur->val); if(cur->left) q.push(cur->left); if(cur->right) q.push(cur->right); } res.push_back(row); } return res; } };

Vertical order:

/** * 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: vector<vector<int>> verticalOrder(TreeNode* root) { vector<vector<int>>res; map<int, vector<int>>map; queue<pair<int, TreeNode*>>q; q.push(make_pair(0, root)); while(!q.empty()) { int qsize = q.size(); //printf("qsize") for(int i = 0; i < qsize; i++) { TreeNode* cur = q.front().second; int tmp = q.front().first; q.pop(); if(cur) map[tmp].push_back(cur->val); if(cur && cur->left) q.push(make_pair(tmp - 1, cur->left)); if(cur && cur->right) q.push(make_pair(tmp + 1, cur->right)); } } for(auto it : map) { res.push_back(it.second); } return res; } };