buildTreeFromInorderPostorder<T> function

BinaryTreeNode<T>? buildTreeFromInorderPostorder<T>(
  1. List<T> inorder,
  2. List<T> postorder
)

Implementation

BinaryTreeNode<T>? buildTreeFromInorderPostorder<T>(
  List<T> inorder,
  List<T> postorder,
) {
  if (inorder.isEmpty || postorder.isEmpty) return null;
  final Map<T, int> inorderIndex = {
    for (var i = 0; i < inorder.length; ++i) inorder[i]: i,
  };
  int postIndex = postorder.length - 1;
  BinaryTreeNode<T>? helper(int left, int right) {
    if (left > right) return null;
    final rootVal = postorder[postIndex--];
    final root = BinaryTreeNode<T>(rootVal);
    final idx = inorderIndex[rootVal]!;
    root.right = helper(idx + 1, right);
    root.left = helper(left, idx - 1);
    return root;
  }

  return helper(0, inorder.length - 1);
}