Pre order, middle order and post order traversal of tree

1. Use a collection to store traversal elements .

The former sequence traversal ：( root – Left – Right )

public int preTraversal(TreeNode root){
    
	List<Integer> list=new ArrayList<>();
	helper(root,list);
	return list;
}
private void helper(TreeNode root,List<Integer> list){
    
	if(root == null) return;
	list.add(root.val);
	if(root.left != null) helper(root.left,list);
	if(root.right != null) hepler(root.right,list);
}

In the sequence traversal

public int preTraversal(TreeNode root){
    
	List<Integer> list=new ArrayList<>();
	helper(root,list);
	return list;
}
private void helper(TreeNode root,List<Integer> list){
    
	if(root == null) return;
	if(root.left != null) helper(root.left,list);
	list.add(root.val);
	if(root.right != null) hepler(root.right,list);
}

After the sequence traversal ：

public int preTraversal(TreeNode root){
    
	List<Integer> list=new ArrayList<>();
	helper(root,list);
	return list;
}
private void helper(TreeNode root,List<Integer> list){
    
	if(root == null) return;
	if(root.left != null) helper(root.left,list);
	if(root.right != null) hepler(root.right,list);
	list.add(root.val);
}

Reconstruction of binary tree ：
According to the result of the preorder and inorder traversal of a binary tree , Build a binary tree and return its root node .
The idea of divide and conquer algorithm ： A scale of N The problem is broken down into k A small-scale problem .
1. Establish root node
2. Construct left and right subtrees
Divide the left and right subtrees according to the root node .

How to divide the left and right subtrees ？

According to the left subtree / The root node of the right subtree 、 Left boundary 、 Right boundary to recursively construct left and right subtrees .

Create a hash table first dic The mapping of the values and indexes traversed in the storage .

HashMap<Integer,Integer> dic=new HashMap<>();