94. Binary Tree Inorder Traversal
Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree [1,null,2,3],
1
\
2
/
3
return [1,3,2].
S1: recursion
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
traversalHelper(root, result);
return result;
}
void traversalHelper(TreeNode* root, vector<int>& result) {
if (!root) {
return;
}
traversalHelper(root->left, result);
result.push_back(root->val);
traversalHelper(root->right, result);
}
S2: iteration using stack 重要！
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> stack;
TreeNode* node = root;
while (node || !stack.empty()) {
while(node) {
stack.push(node);
node = node->left;
}
node = stack.top();
result.push_back(node->val);
stack.pop();
node = node->right;
}
return result;
}
285. Inorder Successor in BST
Given a binary search tree and a node in it, find the in-order successor of that node in the BST.
S: traversal + binary search
注意利用BST特性。in order successor要么为right child的最左支要么为父节点
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
TreeNode* next = NULL;
TreeNode* cur = root;
while (cur) {
if (cur->val == p->val) {
if (cur->right) {
next = cur->right;
while(next && next->left) {
next = next->left;
}
}
return next;
} else if (cur->val > p->val) {
next = cur;
cur = cur->left;
} else if (cur->val < p->val) {
cur = cur->right;
}
}
return NULL;
}
144. Binary Tree Preorder Traversal
Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,2,3].
S1: recursion:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
traversalHelper(root, result);
return result;
}
void traversalHelper(TreeNode* root, vector<int>& result) {
if (!root) {
return;
}
result.push_back(root->val);
traversalHelper(root->left, result);
traversalHelper(root->right, result);
}
S2: iteration using stack
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> stack;
TreeNode* node;
if (root) {
stack.push(root);
}
while (!stack.empty()) {
node = stack.top();
stack.pop();
result.push_back(node->val);
if (node->right) {
stack.push(node->right);
}
if (node->left) {
stack.push(node->left);
}
}
return result;
}
145. Binary Tree Postorder Traversal
Given a binary tree, return the postorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [3,2,1].
S1: recursion
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
traversalHelper(root, result);
return result;
}
void traversalHelper(TreeNode* root, vector<int>& result) {
if (!root) {
return;
}
traversalHelper(root->left, result);
traversalHelper(root->right, result);
result.push_back(root->val);
}
S2: iteration using stack
用preNode记录上次访问的节点以确定现在所处的访问顺序
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> stack;
TreeNode* node;
TreeNode* preNode = NULL; //用preNode记录traversal的方向
if (!root) {
return result;
}
stack.push(root);
while (!stack.empty()) {
node = stack.top();
if (!preNode || preNode->left == node || preNode->right == node) { //情况1:从上往下走
if (node->left) {
stack.push(node->left);
} else if (node->right) { //优先存储左子树，没有左子树才存储右子树
stack.push(node->right);
}
} else if(node->left == preNode && node->right) { //情况2:从左子树往上走，可能有右子树
stack.push(node->right);
} else { //情况3:无右子树或从右子树往上走，左子树要么已经访问过要么为空
result.push_back(node->val);
stack.pop();
}
preNode = node;
}
return result;
}
102. Binary Tree Level Order Traversal
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
S1: BFS with a queue
注意存储每层的size，来确定每层的node数目
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> queue;
vector<vector<int>> result;
if (root) { //避免root为空push进NULL
queue.push(root);
}
while (!queue.empty()) {
int size = queue.size(); //size确定每层的node数目
vector<int> level(size);
for (int i = 0; i < size; ++i) {
TreeNode* node = queue.front();
queue.pop();
level[i] = node->val;
if (node->left) {
queue.push(node->left);
}
if (node->right) {
queue.push(node->right);
}
}
result.push_back(level);
}
return result;
}
314. Binary Tree Vertical Order Traversal
Given a binary tree, return thevertical ordertraversal of its nodes' values. (ie, from top to bottom, column by column).
If two nodes are in the same row and column, the order should be from left to right.
Examples:
Given binary tree
[3,9,20,null,null,15,7],3 /\ / \ 9 20 /\ / \ 15 7
return its vertical order traversal as:
[
[9],
[3,15],
[20],
[7]
]
Given binary tree
[3,9,8,4,0,1,7],3 /\ / \ 9 8 /\ /\ / \/ \ 4 01 7return its vertical order traversal as:
[ [4], [9], [3,0,1], [8], [7] ]Given binary tree
[3,9,8,4,0,1,7,null,null,null,2,5](0's right child is 2 and 1's left child is 5),3 /\ / \ 9 8 /\ /\ / \/ \ 4 01 7 /\ / \ 5 2return its vertical order traversal as:
[ [4], [9,5], [3,0,1], [8,2], [7] ]
S：hashmap + queue
将tree node分配到column，假设root为column i，left child则为column i-1，right child为column i+1. 用hash map记录column idx和对应vector的关系。
因为存储顺序为top to bottom，需要用queue进行level order traversal。用两个queue同步记录node的对应的column idx
vector<vector<int>> verticalOrder(TreeNode* root) {
if (!root) return vector<vector<int>>{};
vector<vector<int>> result;
unordered_map<int, vector<int>> idxToVec;
queue<TreeNode*> nodes;
queue<int> idxs;
int minIdx = INT_MAX;
int maxIdx = INT_MIN;
nodes.push(root);
idxs.push(0);
while (!nodes.empty()) {
TreeNode* node = nodes.front();
nodes.pop();
int idx = idxs.front();
idxs.pop();
minIdx = min(idx, minIdx);
maxIdx = max(idx, maxIdx);
if (idxToVec.find(idx) == idxToVec.end()) {
idxToVec[idx] = vector<int>{node->val};
} else {
idxToVec[idx].push_back(node->val);
}
if (node->left) {
nodes.push(node->left);
idxs.push(idx - 1);
}
if (node->right) {
nodes.push(node->right);
idxs.push(idx + 1);
}
}
for (int i = minIdx; i <= maxIdx; ++i) {
result.push_back(idxToVec[i]);
}
return result;
}
103. Binary Tree Zigzag Level Order Traversal
Given a binary tree, return thezigzag level ordertraversal 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,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
S: level order traversal using queue
因为已知每层node的数目，可以根据是从左到右还是从右到左判断每个node应在的位置
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> result;
if (!root) return result;
queue<TreeNode*> q;
q.push(root);
bool isOddLevel = true;
while (!q.empty()) {
int size = q.size();
vector<int> curLevel(size);
for (int i = 0; i < size; ++i) {
TreeNode* node = q.front();
q.pop();
int idx = isOddLevel? i : size - i - 1;
curLevel[idx] = node->val;
if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}
isOddLevel ^= true;
result.push_back(curLevel);
}
return result;
}
515. Find Largest Value in Each Tree Row
You need to find the largest value in each row of a binary tree.
S: level order traversal using queue
vector<int> largestValues(TreeNode* root) {
vector<int> result;
if (!root) return result;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()) {
int size = q.size();
int curMax = INT_MIN;
for (int i = 0; i < size; ++i) {
TreeNode* node = q.front();
curMax = max(curMax, node->val);
q.pop();
if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}
result.push_back(curMax);
}
return result;
}