How to reconstruct a binary tree in java

Question: Enter the results of pre-order traversal and in-order traversal of a binary tree, please reconstruct the binary tree. It is assumed that the results of the input pre-order traversal and in-order traversal do not contain repeated numbers. For example, if you input the pre-order traversal sequence {1,2,4,7,3,5,6,8} and the in-order traversal sequence {4,7,2,1,5,3,8,6}, then reconstruct the binary tree and return.

Solution analysis:

1. Determine the root node based on preorder traversal of the first node.

2. Find the root node in the in-order traversal and determine the length of the left subtree and the length of the right subtree.

3. According to the length, take the left subtree preorder traversal and the right subtree preorder traversal in the preorder traversal, and take the left subtree inorder traversal and the right subtree inorder traversal in the inorder traversal.

4. Recurse the left subtree and right subtree, and assign the left subtree root node and right subtree root node to the root node.

Free video tutorial recommendation: java learning

Code:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre.length == 0 || in.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(pre[0]);
        for(int i = 0 ; i < in.length; i++) {
            if(in[i] == pre[0]) {
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length)
                ,Arrays.copyOfRange(in,i+1,in.length));
            }
        }
        return root;
    }
}

More related articles tutorial recommendation:Introduction to java programming

The above is the detailed content of How to reconstruct a binary tree in java. For more information, please follow other related articles on the PHP Chinese website!