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

How to rebuild the python binary tree, many novices are not very clear about this, in order to help you solve this problem, the following editor will explain for you in detail, people with this need can come to learn, I hope you can gain something.

Topic description

Enter the results of preorder traversal and mid-order traversal of a binary tree, please reconstruct 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, if you enter the preorder ergodic sequence {1 ~ (th), 2 ~ (th), 4 ~ (th), 7 ~ (th), and 3 ~ (th), then the binary tree is rebuilt and returned.

Train of thought

The first value of the preorder traversal is the value of the root node, which is used to divide the middle order traversal result into two parts, the left part is the order traversal result of the left subtree of the tree, and the right part is the order traversal result of the right subtree of the tree. recursively construct its left and right subtrees respectively.

Code implementation of package Tree

Import java.util.HashMap

/ * rebuild binary tree * enter the results of preorder traversal and mid-order traversal of a binary tree. Please reconstruct 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, if you enter the preorder ergodic sequence {1 ~ (th), 2 ~ (th), 4 ~ (th), 7 ~ (th), and 3 ~ (th), then the binary tree is rebuilt and returned. * / public class Solution54 {private HashMap inOrderNumsIdx = new HashMap (); / / Index corresponding to each value of the ordered traversal array in the cache

Public TreeNode reConstructBinaryTree (int [] pre, int [] in) {for (int I = 0; I)

< in.length; i++) { inOrderNumsIdx.put(in[i], i); } return reConstructBinaryTree(pre, 0, pre.length - 1, in, 0, in.length - 1); } private TreeNode reConstructBinaryTree(int[] pre, int preL, int preR, int[] in, int inL, int inR) { if (preL == preR) return new TreeNode(pre[preL]); if (preL >

PreR | | inL > inR) return null; / / create the current root node and assign TreeNode root = new TreeNode (preprel]; int inIdx = inOrderNumsIdx.get (root.val); int leftTreeSize = inIdx-inL; / / build the left subtree root.left = reConstructBinaryTree (pre, preL + 1, preL + leftTreeSize, in, inL, inL + leftTreeSize-1) / / build the right subtree root.right = reConstructBinaryTree (pre, preL + leftTreeSize + 1, preR, in, inL + leftTreeSize + 1, inR); return root;}

Public class TreeNode {int val; TreeNode left; TreeNode right

TreeNode (int x) {val = x;} is it helpful for you to read the above content? If you want to know more about the relevant knowledge or read more related articles, please follow the industry information channel, thank you for your support.

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.