construct BTree from pre/in/post-order input

Posted on |

pre&in-order input

leetCode105 : given preorder and inorder traversal of a tree, construct the binary tree.

sol: each top node in Btree, has left-branch and right-branch, and each branch is a similar-structure subtree. so every time pop out the top node, and recursive the two subtrees, which return as the left kid and right kid of current top node.

the recursive stopped when the list is empty(in real case, this means the node has only either left or right kid); or stopped when only one element in the list(in real case, the node has both kids, so left or right subtree has only one element).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
TreeNode* sol(list<int>& pre,  list<int>& in)
 {
	 if(pre.empty() || in.empty())
	 {
		 return nullptr; //empty left/right node 
	 }
	 
	 if(pre.size() == 1 && in.size() == 1) 
	 {
			 return new TreeNode(pre.front());
	 }
	 
	 int root = pre.front(); 
	 pre.pop_front(); 
	 TreeNode* root_node = new TreeNode(root); 
	 list<int>::iterator in_it, pre_it; 
	 in_it =  std::find(in.begin(), in.end(), root);
	 if(in_it == in.end()) //only one node in inorder list now, wont happen
	 {
		return (new TreeNode(in.front()));
	 }
	 int idx =  std::distance(in.begin(), in_it);
	 list<int> in_left_subtree(in.begin(), in_it);
	 list<int> in_right_subtree(++in_it, in.end());	
	 in.erase(in_it);
	 
	pre_it = pre.begin(); 
	std::advance(pre_it, idx); 
	
	list<int> pre_left_subtree(pre.begin(), pre_it); 
	list<int> pre_right_subtree(pre_it, pre.end()); 	
	
	root_node->left = sol(pre_left_subtree, in_left_subtree);
	root_node->right = sol(pre_right_subtree, in_right_subtree);
	return root_node; 	 
 }

in each recursive step, I am using exteral containers, same stragey in scramble string. is there a one-swap way?

post/in-order input

leetCode106

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
TreeNode*  sol(list<int>& in,  list<int>& post)
{
	if(in.empty() || post.empty())
		return nullptr; 
	
	if(in.size() == 1 || post.size() == 1)
		return (new TreeNode(in.front())); // return the left || right kid 
	
	//first find out the tree root, the last element in post-order 
	int root_v =  post.back();
	TreeNode* root = new TreeNode(root_v); 
	post.pop_back(); 
	//find root_v in  inorder 
	list<int>::iterator  in_lit =  std::find(in.begin(), in.end(), root_v); 
	
	//create subtrees recursive 
	int left_length =  std::distance(in.begin(), in_lit); 
	list<int> in_left_sub(in.begin(), in_lit); 
	list<int> in_right_sub(++in_lit, in.end()); 
	in.erase(in_lit); 
	list<int>::iterator post_lit = std::next(post.begin(), left_length); 
	list<int> post_left_sub(post.begin(), post_lit);
	list<int> post_right_sub(post_lit, post.end()); 
	
	root->left = sol(in_left_sub, post_left_sub); 
	root->right = sol(in_right_sub, post_right_sub);
	return root ;
}