Leetcode105. 从前序与中序遍历序列构造二叉树

题目传送：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

运行效率

代码如下

class Solution {
   public TreeNode buildTree(int[] preorder, int[] inorder) {
    // 1、先序序列的第一个值就是二叉树的根节点
    int val = preorder[0];
    TreeNode root = new TreeNode(val);
    // 2、然后在中序序列里面找到对应值，然后就可以把中序序列切分成2半
    int index = findIndex(inorder, val);
    //左子树的节点数
    int leftChildLength =index;
    //右子树的节点数
    int rightChildLength =inorder.length-index-1;

    //先处理左子树
    if (leftChildLength>0) {
      // 中序序列中 关于左子树的部分
      int[] inOrderFirstArray = Arrays.copyOf(inorder, leftChildLength);
      // 前序序列中 关于左子树的部分
      int[] preOrderFirstArray = Arrays.copyOfRange(preorder, 1,leftChildLength+1);
      TreeNode leftChild = buildTree(preOrderFirstArray, inOrderFirstArray);
      root.left = leftChild;
    }
    //再处理右子树
    if(rightChildLength>0){
      // 中序序列中  关于右子树的部分
      int[] inOrderSecondArray = Arrays.copyOfRange(inorder, index + 1, inorder.length);
      // 前序序列中  关于右子树的部分
      int[] preOrderSecondArray = Arrays.copyOfRange(preorder, leftChildLength+1, inorder.length);
      TreeNode rightChild = buildTree(preOrderSecondArray, inOrderSecondArray);
      root.right = rightChild;
    }
    return root;
  }

  public int findIndex(int[] inorder, int val) {
    for (int i = 0; i < inorder.length; i++) {
      if (inorder[i] == val) {
        return i;
      }
    }
    return -1;
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42