Cabbage Java self study room covers core knowledge

LeetCode Series of Algorithms (Java version) 106. A binary tree is constructed by traversing sequences of middle and rear order

Force buckles the original problem

105. 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.

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]Copy the code

Return the following binary tree:

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

Divide and conquer method

Many problems related to binary tree have the idea of divide and conquer in it.

The idea of divide-and-conquer method: the original problem is disassembled into several smaller sub-problems with the same structure as the original problem. After the sub-problems are solved, the original problem can be solved.

Their thinking

First of all, we must have a question: why with the results of pre-order traversal and middle-order traversal, we can define and construct the entire binary tree?

First, let’s review the definition of pre-order traversal and middle-order traversal:

  • The order of the preceding traversal is root node -> left subtree -> right subtree.
  • The middle order traversal is left subtree -> root node -> right subtree.

Note: there are some overlaps between the root node -> left subtree of the preordered traversal population and the left subtree -> root node of the middle-ordered traversal population, and these overlaps are the key to our reasoning to find the law.

Let’s use a more complex example to analyze the solution idea clearly:

Foreorder traversal =[1,2,4,7,3,5,6,8] middle order traversal =[4,7,2,1,5,3,8,6]Copy the code

When we have clearly obtained the results of pre-order traversal and middle-order traversal, we can deduce the following rules according to the characteristics of binary trees:

  1. Both preorder traversal and middle order traversal are traversal results of the same tree, and the node definitions of the tree in the two results are consistent.

  2. The first number in the preceding traversal must be the root of the entire binary tree, as in the example 1.

  3. If 1 is the root of the entire binary tree, and 1 in the middle-order traversal is also the root of the entire binary tree, its left [4,7,2] is the left subtree, and its right [5,3,8,6] is the right subtree.

  4. Under the same root node 1, the number of nodes in the left and right subtrees of the root node must be the same in the results of pre-order traversal and middle-order traversal. The left subtree [4,7,2] of middle-order traversal has 3 nodes, and the right subtree [5,3,8,6] has 4 nodes, so the left subtree of pre-order traversal also has 3 nodes [2,4,7]. The right subtree also has 4 nodes [3,5,6,8];

  5. At this point, the problem has been divided into several small identical problems, which can obviously be treated as a recursive structure.

  • First of all, the root of the binary tree is zero1;
  • The root node1And the result of the preceding traversal is,4,7 [2], the result of middle-order traversal is,7,2 [4];
  • The root node1The result of the preceding traversal is,5,6,8 [3], the result of middle-order traversal is,3,8,6 [5];

  1. How to delimit an array, we can define different subscripts (cursors) to achieve coding. Front order traverses left and rightpreLeft,preRight, the middle order traverses left and rightinLeft,inRight.

Code implementation

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

    TreeNode(intx) { val = x; }}public class Solution {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int preLen = preorder.length;
        int inLen = inorder.length;
        if(preLen ! = inLen) {throw new RuntimeException("Incorrect input data.");
        }
        return buildTree(preorder, 0, preLen - 1, inorder, 0, inLen - 1);
    }


    /** * Construct a binary tree ** using preorder for all elements in index range [preLeft, preRight] and inorder for all elements in index range [inLeft, inRight]@paramPreorder result of preorder traversal of binary tree *@paramPreLeft left boundary * of the result of preLeft binary tree traversal@paramPreRight The right edge of the result of pre-traversal of the binary tree *@paramInorder Result of backorder traversal in binary tree *@paramInLeft Left boundary * of the result of the back-order traversal of the binary tree@paramInRight The right boundary * of the result of the back-order traversal of the binary tree@returnThe root of the binary tree */
    private TreeNode buildTree(int[] preorder, int preLeft, int preRight,
                               int[] inorder, int inLeft, int inRight) {
        // Since this is a recursive call, write the recursive termination condition first
        if (preLeft > preRight || inLeft > inRight) {
            return null;
        }
        // The starting element of the preorder traversal is important
        int pivot = preorder[preLeft];
        TreeNode root = new TreeNode(pivot);
        int pivotIndex = inLeft;
        // Strictly speaking, it is necessary to determine whether the array index pivotIndex < inRight
        while(inorder[pivotIndex] ! = pivot) { pivotIndex++; } root.left = buildTree(preorder, preLeft +1, pivotIndex - inLeft + preLeft,
                inorder, inLeft, pivotIndex - 1);
        root.right = buildTree(preorder, pivotIndex - inLeft + preLeft + 1, preRight,
                inorder, pivotIndex + 1, inRight);
        returnroot; }}Copy the code

Complexity analysis

  • Time complexity: O(N2)O(N^2)O(N2), where NNN is the number of nodes in the binary tree. Every time the recursive method is called to create a node, a total of NNN nodes are created. Finding the position of the root node in the middle order traversal is related to NNN, and the time occupied by the recursive method is not calculated.

  • Space complexity: O(1)O(1)O(1) where the space occupied by recursive methods is not calculated.

LeetCode Series of Algorithms (Java version) 106. A binary tree is constructed by traversing sequences of middle and rear order