Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
-----------------------------------------------
Explaination
Having a start and an end pointer for each array.
Using hash table to track the root position in inorder array.
For preorder array, the first in partition is always the root node, for inorder one, in a given partition, all nodes whose indexes are less than root's are belong to its left child, whose indexes are greater than root's, belongs to its right child
Same algorithm for Postorder and Inorder combination
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void hashMapping(vector<int> &inorder, unordered_map<int,int>& mapping){
for (int i = 0; i < inorder.size(); i++) {
int k = inorder[i];
mapping[k] = i;
}
}
TreeNode *rec(vector<int> &preorder, vector<int> &inorder, int startP, int endP, int startI, int endI,unordered_map<int,int>& mapping) {
//if (endI < startI || endP < startP)return NULL;
int rootIndex = mapping[preorder[startP]];
TreeNode *root = new TreeNode(preorder[startP]);
// delimiter for preorder
int delimiterIndex = rootIndex - startI + startP;
if (rootIndex > startI) {
root->left = rec(preorder,inorder,startP+1,delimiterIndex,startI,rootIndex - 1,mapping);
}else {
root->left=NULL;
}
if (rootIndex < endI) {
root->right = rec(preorder,inorder,delimiterIndex + 1,endP,rootIndex + 1,endI,mapping);
}else {
root->right=NULL;
}
return root;
}
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
// Note: The Solution object is instantiated only once and is reused by each test case.
if (preorder.size() == 0) return NULL;
unordered_map<int,int> mapping;
hashMapping(inorder,mapping);
return rec(preorder,inorder,0,preorder.size()-1,0,inorder.size()-1,mapping);
}
};
Construct Binary Tree from Inorder and Postorder Traversal
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
-----------------------------
Similar to Preorder and Inorder combination
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void hashMapping(vector<int> &inorder, unordered_map<int,int>& mapping){
for (int i = 0; i < inorder.size(); i++) {
int k = inorder[i];
mapping[k] = i;
}
}
TreeNode *rec(vector<int> &postorder, vector<int> &inorder, int startP, int endP, int startI, int endI,unordered_map<int,int>& mapping) {
//if (endI < startI || endP < startP)return NULL;
int rootIndex = mapping[postorder[endP]];
TreeNode *root = new TreeNode(postorder[endP]);
// delimiter for postorder
int delimiterIndex = rootIndex - startI + startP-1;
if (rootIndex > startI) {
root->left = rec(postorder,inorder,startP,delimiterIndex,startI,rootIndex - 1,mapping);
}else {
root->left=NULL;
}
if (rootIndex < endI) {
root->right = rec(postorder,inorder,delimiterIndex + 1,endP-1,rootIndex + 1,endI,mapping);
}else {
root->right=NULL;
}
return root;
}
TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
// Note: The Solution object is instantiated only once and is reused by each test case.
if (postorder.size() == 0) return NULL;
unordered_map<int,int> mapping;
hashMapping(inorder,mapping);
return rec(postorder,inorder,0,postorder.size()-1,0,inorder.size()-1,mapping);
}
};
Binary Tree Level Order Traversal II
Given a binary tree, return the
bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree
{3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its bottom-up level order traversal as:
[
[15,7]
[9,20],
[3],
]
----------------------------------
Similar to #102 Binary Tree Level Order Traversal
This is a DFS solution
/**
* 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<vector<int> > levelOrderBottom(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<vector<int>> result;
traverse(root, 1, result);
std::reverse(result.begin(), result.end());
return result;
}
void traverse(TreeNode *root, int level, vector<vector<int>> &result) {
if (root == NULL) {
return;
}
if (level > result.size()) {
vector<int> v;
result.push_back(v);
}
result[level-1].push_back(root->val);
traverse(root->left,level+1,result);
traverse(root->right,level+1,result);
}
};
Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
For example,
Given
1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6
----------------------------------------------------------
Solution #1, not in place, preorder traverse the tree, store each node in an array,
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void traverse (TreeNode *root, vector<TreeNode*>& v) {
if (root != NULL) {
v.push_back(root);
traverse(root->left,v);
traverse(root->right,v);
}
}
void flatten(TreeNode *root) {
// Note: The Solution object is instantiated only once and is reused by each test case.
vector<TreeNode*> v;
traverse(root,v);
TreeNode *itr = root;
for (int i = 1; i < v.size(); i++) {
itr->right = v[i];
itr->left = NULL;
itr = itr->right;
}
}
};
Solution #2, in place iterative.
Same logic can be adopted in recursive implementation
O(n), 在inner loop里面，在整段代码的执行过程中每个node只出现过一次
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void flatten(TreeNode *root) {
// Note: The Solution object is instantiated only once and is reused by each test case.
TreeNode* ret = root;
while (root != NULL) {
if (root->left != NULL) {
TreeNode *right = root->right;
TreeNode *mostRight = root->left;
while (mostRight->right != NULL) {
mostRight = mostRight->right;
}
mostRight->right = right;
root->right = root->left;
root->left = NULL;
}
root = root->right;
}
root = ret;
}
};
Update on Sep-28-2014
Recursive solution, Pre-Order tree 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:
TreeNode* f(TreeNode *root, TreeNode *newRoot) {
if (root == NULL) return newRoot;
TreeNode *tempRight = root->right;
newRoot->right = root;
TreeNode *t = f(root->left,root); // return the end of list
root->left = NULL;
TreeNode *t2 = f(tempRight,t);
return t2;
}
void flatten(TreeNode *root) {
TreeNode *newRoot = root;
TreeNode *dummy = new TreeNode(0);
f(newRoot,dummy);
}
};
Updated on Sep-24th-2018
跟上面类似思路，更易懂的写法。getEndOfList(root)返回以root为顶点的sub-tree转换成为list之后的最尾端的点
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public void flatten(TreeNode root) {
if (root == null) return;
getEndOfList(root);
}
private TreeNode getEndOfList(TreeNode root) {
TreeNode l = root.left;
TreeNode r = root.right;
if (root.left != null) {
TreeNode end = getEndOfList(root.left);
root.right = l;
l = end;
end.right = r;
root.left = null;
}
if (r != null) {
return getEndOfList(r);
}
if (l == null) {
return root;
}
return l;
}
}
