Two questions: Leetcode105, constructing binary trees from pre-order and middle-order traversal sequences, LeetCode106, constructing binary trees from middle-order and post-order traversal sequences, Java edition

The article directories

• • • Construct a binary tree by traversing pre-order and middle-order sequences
    • A binary tree is constructed by traversing sequences of middle and rear order

Binary tree traversal is also recursive traversal (to get a sequence from the tree), and binary tree construction is also recursive construction (to get a binary tree from the sequence).

A binary tree can be uniquely determined by preorder traversal number group and middle order traversal number group. A binary tree can be uniquely determined by the middle-order traversal number group and the post-order traversal number group. However, a binary tree cannot be uniquely determined by the antecedent traversal number group and the post traversal number group.

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.

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

/**
 * Definition forA binary tree node. * public class TreeNode {// leecode provides a binary tree for you to use * 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; Put (inorder[I], I) {// Put (inorder[I], I) {// Put (inorder[I], I); } // Six parameters, preorder three, inorder threereturn 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) {		
		if(preEnd<preStart||inEnd<inStart)
			returnnull; TreeNode node=new TreeNode(preorder[preStart]); Int I =map.get(preorder[preStart]); int I =map.get(preorder[preStart]); Int leftlen= i-instart; int leftlen= i-instart; // I-instart changes to the length of the left side of the middle order traversal, i.e. the length of the left subtree. Node. left=buildTree(preorder, preStart+1, preStart+leftlen, map, inStart, i-1); Node. right=buildTree(preOrder, preStart+leftlen+1,preEnd, map, I +1, inEnd);returnnode; }}Copy the code

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

Node. left=buildTree(preorder, preStart+1, preStart+1+leftlen, map, inStart, i-1); Before the return buildTree (preorder, 0, preorder. Length – 1, map, 0, inorder. Length – 1);

PreStart =0, now preStart+1 Because we get rid of a root node, good

Preorder. Length-1: preStart+leftlen The left subtree is preorder[preStart+1]. The left subtree is preorder[preStart+1, (preStart+1)+(leftlen-1)] becomes preOrder [preStart+1, preStart+leftlen], leftlen is the length of the left subtree

Mid-order sequence starting point: Why inStart=0 before and now? Since the left subtree of the middle traversal is already on the left, it’s ok to start from the left, good

Middle sequence endpoint: why is the right subtree endpoint inorder.length-1 now i-1? Because the root node is I, the left subtree of all middle-order traversals ends at i-1, good

Return value: Why return the value node.left? The root node of the subtree, node, is the left root node of the mother tree.

Node. right=buildTree(preOrder, preStart+leftlen+1,preEnd, map, I +1, inEnd); Before the return buildTree (preorder, 0, preorder. Length – 1, map, 0, inorder. Length – 1);

PreStart +leftlen+1 preStart=0 It was the whole tree, now it’s the right subtree, and the right subtree root node starts at preStart+leftlen+1.

Preorder. Length-1: why is it preEnd(preorder. Length-1)? For antecedent sequences (middle left and right), the root node is first and the end of the entire tree is the same as the end of the right subtree.

Mid-order sequence starting point: why inStart=0, now I +1? Because the whole tree before, the middle-order traversal starts at subscript 0, and now it’s the right subtree, and I just figured out that the root identifies I under the middle-order sequence, so in the right subtree, the middle-order sequence starts at (I +1).

Middle sequence terminus: why is the right subtree terminus inorder.length-1 now inEnd(i.e. inorder.length-1)? For middle-ordered sequences (left-middle-right), where the root node is in the middle, the end of the entire tree is the same as the end of the right subtree.

Return value: Why is the value node.right returned? For the right subtree, node, the root node of the subtree, is node.right, the left root node of the mother tree.

In order to change the middle sequence from an array to a map, why does the new map have a key that stores array elements and a value that stores array subscripts? This is determined by the search nature of the map data structure. In map, a unique value can be found according to the key, but a unique key cannot be found through the value. After determining the root node through the pre-order sequence, the position of the root node must be determined through the mid-order sequence, so the value can only be subscripted. Element in key.

Why does the buildTree() method finally return a node? This node is the root node of the whole tree. After the whole tree is built, the root node is returned. Why? Since only from this root can the entire tree be traversed (pre-traversal, mid-traversal, or post-traversal), returning the root of the entire tree is equivalent to returning the entire binary tree.

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

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

/**
 * 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); // The first three arguments are post-ordered, and the last three arguments are middle-orderedreturn 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) {
		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

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