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

链接：105.从前序与中序遍历序列构造二叉树
难度：Medium
标签：树、数组、哈希表、分治、二叉树
简介：根据一棵树的前序遍历与中序遍历构造二叉树。

题解 1 - java

• 编辑时间：2020-02-21
• 执行用时：26ms
• 内存消耗：76.4MB
• 编程语言：java
• 解法介绍：使用递归，通过切割数组进行遍历左右节点。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
	public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length==0)return null;
		int center = preorder[0];
		TreeNode node = new TreeNode(center);
		int index=indexOf(inorder, center);
		int left = index-0,right=inorder.length-1-index;
		if(left!=0) {
			node.left=buildTree(split(preorder,1,left), subString(inorder, 0,index));
		}
		if(right!=0) {
			node.right=buildTree(subString(preorder,1+left), subString(inorder, index+1));
		}
		return node;
	}
	public int[] split(int[] arr,int start,int length) {
		int[] newArr = new int[length];
		for(int i=0;i<length;i++) {
			newArr[i]=arr[start];
			start++;
		}
		return newArr;
	}
	public int indexOf(int[] arr, int num) {
		for (int i = 0, len = arr.length; i < len; i++) {
			if (arr[i] == num)
				return i;
		}
		return -1;
	}
	public int[] subString(int[] arr, int start) {
		return subString(arr, start, arr.length);
	}
	public int[] subString(int[] arr, int start, int end) {
		int length = end - start;
		int[] newArr = new int[length];
		for (int i = 0; i < length; i++) {
			newArr[i] = arr[start];
			start++;
		}
		return newArr;
	}
}

题解 2 - python

• 编辑时间：2024-02-20
• 执行用时：137ms
• 内存消耗：86.3MB
• 编程语言：python
• 解法介绍：dfs。

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder: return None
        index = inorder.index(preorder[0])
        return TreeNode(
            preorder[0], 
            self.buildTree(preorder[1:index + 1], inorder[:index]),
            self.buildTree(preorder[index + 1:], inorder[index + 1:])
        )