Shulou(Shulou.com)06/03 Report--

The main content of this article is to explain how to rebuild the binary tree in LeetCode. Interested friends may wish to have a look at it. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn how to rebuild the binary tree with the solution of LeetCode.

Title

Enter the results of preorder traversal and mid-order traversal of a binary tree, please rebuild the binary tree. Assume that the results of both the preorder traversal and the intermediate traversal of the input do not contain duplicate numbers.

For example, give the

Preorder traversal preorder = [3pm 9pm 20je 15rem 7]

Traversing in the middle order inorder = [9 ~ 1 ~ 3 ~ 15 ~ 20 ~ 7]

Return the following binary tree:

3 / 9 20 / 15 7

Answer to the question

Last week, we talked about pre-order traversal and post-order traversal, in fact, this pre-order, mid-order, and post-order are all relative to the processing order of intermediate nodes.

For example, the order of traversal in the first order should be:

[root node | left subtree | right subtree]

In the same way, the order of traversal in the middle order is:

[left subtree | Root node | right subtree]

So the first element of the preorder traversal must be the root node.

Then, we can find the root node in the middle order traversal, and correctly divide the middle order ergodic area into three parts, that is, the left subtree middle order, the root node, and the right subtree middle order.

For example:

If there are only three elements, then it can end here, because the tree can already be drawn.

For example, the preface is [3pd9re20], and the middle preface is [9pd3re20]

We know the root node 3 according to the middle order, and then we can distinguish the left subtree node 9, the root node 3 and the right subtree node 20 in the middle order.

Now we spread out, what if there are more than three nodes?

Example 2:

If it is five elements, for example, the preorder is [3pyrrine 9pd20rem 15rem 7], and the middle preface is [9pdm 3pr 15je 20je 7]

After the first division, we divide the middle order into the left subtree 9, the root node 3, and the right subtree.

At this time, how to divide the right sub-tree? What are the following nodes? I don't know again.

So at this time, we need to relate to the preorder traversal, and according to the left subtree nodes we know, the right subtree in the preorder should be [20], so the root node of the right subtree is 20.

In short, the preorder and intermediate order help each other, and finally build our tree through recursion.

Solution 1

Solution 1 depends on recursion.

The recursive process is to find the left and right child tree nodes of each parent node, with a total of three values.

The final value is taken from the pre-order list, which is actually the parent node of each small tree.

The function of the mid-order traversal array is to find the position of each parent node in the mid-order traversal array.

The following algorithm is obtained.

/ * Definition for a binary tree node. * public class TreeNode {* int val; * TreeNode left; * TreeNode right; * TreeNode (int x) {val = x;} *} * / class Solution {int [] preorder; HashMap dic = new HashMap (); public TreeNode buildTree (int [] preorder, int [] inorder) {this.preorder = preorder; for (int I = 0; I)

< inorder.length; i++) dic.put(inorder[i], i); return recur(0, 0, inorder.length - 1); } TreeNode recur(int root, int left, int right) { if(left >

Right) return null; / / root node TreeNode node = new TreeNode; / / split point int I = dic.get (preroot); node.left = recur (root + 1, left, I-1); node.right = recur (root + I-left + 1, I + 1, right) Return node;}}

Note that each time you take the root node of the right subtree:

The node number of the left subtree is i-left.

So in the preorder traversal array, the node + root node position of the left subtree is the last node position of the left subtree, that is, root+i-left.

Finally, it is concluded that the root node of the right subtree is root + I-left + 1.

The end condition of recursion is that the left and right subtree nodes meet, that is, left > right.

Time complexity

O (n), n is the number of nodes in the tree.

Space complexity

O (N), using HashMap.

Solution 2

There is also a method called iterative method, which is very ingenious, and it took a long time to figure out the official answer, .

Its main idea is to understand the rules of preorder traversal and mid-order traversal, and then take values from preorder traversal one by one and put them in the appropriate position.

For example, the following binary tree:

3 / 9 20 / 8 15 7 / 5 10 / 4

After traversing the preorder, we can find that the leftmost node is listed first, that is, 3pc9pr 8je 5pr 4

The middle order list is the opposite, starting at the bottom of the leftmost, up the column, and if you find that a node has a right child node, start to the right column.

For example, 4, 5, 5, 8. At this point, it is found that 8 has a right child node, so start counting 10, and then continue to the leftmost up, 9pr 3.

Finally, list the complete preorder and intermediate order:

Preorder = [3,9,8,5,4,10,20,15,7] inorder = [4,5,8,10,9,3,15,20,7]

In short, the front order starts from the left column and goes down from the top. The middle order starts from the left column and from the bottom to the top.

Look at the code:

Class Solution {public TreeNode buildTree (int [] preorder, int [] inorder) {if (preorder = = null | | preorder.length = = 0) {return null;} TreeNode root = new TreeNode (preorder [0]); Deque stack = new LinkedList (); stack.push (root); int inorderIndex = 0; for (int I = 1; I < preorder.length) Int preorderVal +) {int preorderVal = preorder [I]; TreeNode node = stack.peek (); if (node.val! = inorder [inorderIndex]) {node.left = new TreeNode (preorderVal); stack.push (node.left) } else {while (! stack.isEmpty () & & stack.peek (). Val = = inorder [inorderIndex]) {node = stack.pop (); inorderIndex++;} node.right = new TreeNode (preorderVal); stack.push (node.right) }} return root;}}

The if statement is to find the last node in the left column, such as 4 in the above example.

The while loop is to find the parent node of the right node when it is found that there is a right node, and then add it.

At this point, I believe you have a deeper understanding of "how to rebuild the binary tree in LeetCode". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.