106.从中序与后序遍历序列构造二叉树

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

题解 1 - java

• 编辑时间：2020-02-21
• 执行用时：18ms
• 内存消耗：75.9MB
• 编程语言：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[] inorder, int[] postorder) {
		if (inorder.length == 0)
			return null;
		int center = postorder[postorder.length - 1];
		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(subString(inorder, 0, index), split(postorder, 0, left));
		}
		if (right != 0) {
			node.right = buildTree(subString(inorder, index + 1), split(postorder, 0 + left, right));
		}
		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 - typescript

• 编辑时间：2020-09-25
• 执行用时：196ms
• 内存消耗：111.2MB
• 编程语言：typescript
• 解法介绍：递归。

function buildTree(inorder: number[], postorder: number[]): TreeNode | null {
  if (inorder.length === 0 && postorder.length === 0) return null;
  const val = postorder[postorder.length - 1];
  const inorderIndex = inorder.indexOf(val);
  const lInorder = inorder.slice(0, inorderIndex);
  const rInorder = inorder.slice(inorderIndex + 1);
  const lPostorder = postorder.slice(0, lInorder.length);
  const rPostorder = postorder.slice(lInorder.length, postorder.length - 1);
  return new TreeNode(val, buildTree(lInorder, lPostorder), buildTree(rInorder, rPostorder));
}

题解 3 - python

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

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