Wechat search: Bigsai good article to share the first time

preface

In the interview process, we often encounter some data structure related questions, many classic questions can be asked. And the data structure of sorting, linked list, binary tree and other problems are enduring, this is not, today to share a classic problem: given two sequences how to construct a binary tree.

Tips: When encountering binary tree related problems, most of them are related to recursion

Construct a binary tree by traversing pre-order and middle-order sequences

The binary tree is constructed according to the pre-order traversal and middle-order traversal of a tree. Of course, it is also the original problem of 105.

Note: You can assume that there are no duplicated elements in the tree.

For example, given

Preorder = [3,9,20,15,7]

Inorder = [9,3,15,20,7]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7
Copy the code

Analysis: Given a pre-ordered sequence and a middle-ordered sequence with no repeating elements, how do we construct one – and binomial trees? We can first observe the characteristics of the two sequences separately:

Fore-order traversal: Traversal rules are (root, [left region], [right region]). Middle-order traversal: Traversal rules are ([left region], root, [right region]).

The left region of the preceding order traversal and the left region of the middle order traversal contain the same range of elements, and the roots are the same. So you can do something like this:

  1. The root can be determined by finding the root node at the first of the preceding traversals.
  2. Find the value of the root node through middle-order traversal, so that we can know the number of nodes in the left region and the right region.
  3. The left region of the root node is determined by the left region determined by the pre-middle sequence, and the right node of the root node is determined by the right region determined by the pre-middle sequence.

Some operations can be understood with the help of this diagram:

In practice, you can use a HashMap to store sequential sequences to avoid double-counting. The code is as follows:

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; }} * * /
class Solution {
   public TreeNode buildTree(int[] preorder, int[] inorder) {
		if(preorder.length==0)
			return null;
		TreeNode root=new TreeNode(preorder[0]);
		Map<Integer, Integer>map=new HashMap<Integer, Integer>();
		for(int i=0; i<inorder.length; i++) { map.put(inorder[i], i); }return buildTree(preorder,0,preorder.length-1, map,0,inorder.length-1);
    }

	private TreeNode buildTree(int[] preorder, int preStart, int preEnd, Map<Integer, Integer> map, int inStart, int inEnd) {
		// TODO Auto-generated method stub
		if(preEnd<preStart||inEnd<inStart)
			return null;
		TreeNode node=new TreeNode(preorder[preStart]);
		int i=map.get(preorder[preStart]);// Node value
		
		int leftlen=i-inStart;// The length of the left side
		node.left=buildTree(preorder, preStart+1, preStart+1+leftlen, map, inStart, i-1);
		node.right=buildTree(preorder, preStart+leftlen+1,preEnd, map, i+1, inEnd);
		returnnode; }}Copy the code

A binary tree is constructed by traversing sequences of middle and rear order

According to the middle order traversal and post order traversal of a tree to construct a binary tree, force button 106 questions

Note: You can assume that there are no duplicated elements in the tree.

For example, given

Inorder = [9,3,15,20,7]

Postorder = [9,15,7,20,3]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7
Copy the code

Analysis: with the above analysis, then through a post-order traversal and middle-order traversal to construct a binary tree, in fact, the principle is the same as the previous.

Back-order traversal: Traversal rules are ([left region], [right region], root). Middle-order traversal: Traversal rules are ([left region], root, [right region]).

The specific implementation code is:

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; }} * * /
class Solution {
   public TreeNode buildTree(int[] inorder,int[] postorder) {
		if(postorder.length==0)
			return null;
		Map<Integer, Integer>map=new HashMap<Integer, Integer>();
		for(int i=0; i<inorder.length; i++) { map.put(inorder[i], i); }return buildTree(postorder,0,postorder.length-1, map,0,inorder.length-1);
    }

	private TreeNode buildTree(int[] postorder, int postStart, int postEnd, Map<Integer, Integer> map, int inStart, int inEnd) {
		// TODO Auto-generated method stub
		if(postEnd<postStart||inEnd<inStart)
			return null;
		TreeNode node=new TreeNode(postorder[postEnd]);
		int i=map.get(postorder[postEnd]);
		
			
		int leftlen=i-inStart;
		
		node.left=buildTree(postorder, postStart,postStart+leftlen-1, map, inStart, i-1);
		node.right=buildTree(postorder, postStart+leftlen,postEnd-1, map, i+1, inEnd);           returnnode; }}Copy the code

Original is not easy, Bigsai please help me with two things:

Like to support, you are sure to be my platform in the creation of a steady power.

Wechat search “Bigsai”, reply bigsai white whoring ebook, let’s see you next time!