Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example: Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
思路： 使用两个队列（一个可以顺序读，所以用vector模拟），每个队列放一层结点。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
void getQue1(vector<TreeNode*> &q1, queue<TreeNode*> &q2, vector<vector<int> > &vec) {
while(!q2.empty()) {
TreeNode *p = q2.front();
q2.pop();
if(p->left) q1.push_back(p->left);
if(p->right) q1.push_back(p->right);
}
if(q1.size() == 0) return;
vector<int> vec2;
for(int i = q1.size()-1; i >= 0; --i)
vec2.push_back(q1[i]->val);
vec.push_back(vec2);
}
void getQue2(queue<TreeNode*> &q2, vector<TreeNode*> &q1, vector<vector<int> > &vec) {
if(q1.size() == 0) return;
vector<int> vec2;
for(int i = 0; i < q1.size(); ++i) {
if(q1[i]->left) { q2.push(q1[i]->left); vec2.push_back(q1[i]->left->val); }
if(q1[i]->right) { q2.push(q1[i]->right); vec2.push_back(q1[i]->right->val); }
}
if(vec2.size()) vec.push_back(vec2);
q1.clear();
}
class Solution {
public:
vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
vector<vector<int> > vec;
if(root == NULL) return vec;
queue<TreeNode*> q2;
vector<TreeNode*> q1;
q2.push(root);
vec.push_back(vector<int>(1, root->val));
while(!q2.empty()) {
getQue1(q1, q2, vec);
getQue2(q2, q1, vec);
}
return vec;
}
};
Binary Tree Inorder Traversal
OJ: https://oj.leetcode.com/problems/binary-tree-inorder-traversal/
Given a binary tree, return the inorder traversal of its nodes' values.
For example: Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
题解： 两种方法： 1. 使用栈: O(n) Time, O(n) Space。 2. Morris traversal (构造线索树), O(n) Time, O(1) Space.
1. 使用栈
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
vector<int> vec;
if(root == NULL) return vec;
TreeNode *p = root;
stack<TreeNode *> st;
st.push(p);
while(p->left) { p = p->left; st.push(p); }
while(!st.empty()) {
TreeNode *q = st.top();
st.pop();
vec.push_back(q->val);
if(q->right) {
q = q->right; st.push(q);
while(q->left) { q = q->left; st.push(q); }
}
}
return vec;
}
};
2. Morris Traversal
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
vector<int> vec;
TreeNode *cur, *pre;
cur = root;
while(cur) {
if(cur->left == NULL) {
vec.push_back(cur->val);
cur = cur->right;
} else {
pre = cur->left;
while(pre->right && pre->right != cur) pre = pre->right;
if(pre->right == NULL) {
pre->right = cur;
cur = cur->left;
} else {
pre->right = NULL;
vec.push_back(cur->val);
cur = cur->right;
}
}
}
return vec;
}
};