Preorder:
Approach #1: Recurisive.
/**
* 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<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
helper(root, ans);
return ans;
}
private:
void helper(TreeNode* root, vector<int>& ans) {
if (root == NULL) return ;
ans.push_back(root->val);
helper(root->left, ans);
helper(root->right, ans);
}
};
Approach #2: Iteratively.[Java]
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new LinkedList<Integer>();
Stack<TreeNode> todo = new Stack<TreeNode>();
TreeNode cur = root;
while (cur != null) {
res.add(cur.val);
if (cur.right != null) {
todo.push(cur.right);
}
cur = cur.left;
if (cur == null && !todo.isEmpty()) {
cur = todo.pop();
}
}
return res;
}
}
Approach #3: Morris Traversal.[C++]
/**
* 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<int> preorderTraversal(TreeNode* root) {
TreeNode* cur = root;
vector<int> nodes;
while (cur) {
if (cur->left) {
TreeNode* pre = cur->left;
while (pre->right && (pre->right != cur)) {
pre = pre->right;
}
if (!(pre->right)) {
nodes.push_back(cur->val);
pre->right = cur;
cur = cur->left;
} else {
pre->right = NULL;
cur = cur->right;
}
} else {
nodes.push_back(cur->val);
cur = cur->right;
}
}
return nodes;
}
};
Using Morris Traversal can don't use recurisive and stack and space complex is O(1).
inorder
Approach #1: Java.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList< > ();
Stack<TreeNode> stack = new Stack< > ();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
res.add(curr.val);
curr = curr.right;
}
return res;
}
}
postorder
Approach #2: C++.
/**
* 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<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> todo;
vector<int> res;
TreeNode* node = root;
TreeNode* last = NULL;
while (node || !todo.empty()) {
if (node) {
todo.push(node);
node = node->left;
} else {
TreeNode* top = todo.top();
if (top->right && top->right != last) {
node = top->right;
} else {
res.push_back(top->val);
last = top;
todo.pop();
}
}
}
return res;
}
};
Binary Tree Level Order Traversal
Approach #1: C++. [Using queue]
/**
* 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>> ans;
queue<TreeNode*> q;
if (root == NULL) return ans;
q.push(root);
while (!q.empty()) {
int size = q.size();
vector<int> dummy;
for (int i = 0; i < size; ++i) {
TreeNode* node = q.front();
if (node->left != NULL) q.push(node->left);
if (node->right != NULL) q.push(node->right);
dummy.push_back(node->val);
q.pop();
}
ans.push_back(dummy);
}
return ans;
}
};
Approach #2: Java. [Using recursive.]
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
levelHelper(res, root, 0);
return res;
}
public void levelHelper(List<List<Integer>> res, TreeNode root, int height) {
if (root == null) return;
if (height >= res.size()) {
res.add(new LinkedList<Integer>());
}
res.get(height).add(root.val);
levelHelper(res, root.left, height + 1);
levelHelper(res, root.right, height + 1);
}
}