Construct Binary Tree from Preorder and Inorder Traversal

描述

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:You may assume that duplicates do not exist in the tree.

分析

无

代码

  1. // Construct Binary Tree from Preorder and Inorder Traversal
  2. // 递归，时间复杂度O(n)，空间复杂度O(\logn)
  3. public class Solution {
  4.     public TreeNode buildTree(int[] preorder, int[] inorder) {
  5.         return buildTree(preorder, 0, preorder.length,
  6.                 inorder, 0, inorder.length);
  7.     }
  9.     TreeNode buildTree(int[] preorder, int begin1, int end1,
  10.                        int[] inorder, int begin2, int end2) {
  11.         if (begin1 == end1) return null;
  12.         if (begin2 == end2) return null;
  14.         TreeNode root = new TreeNode(preorder[begin1]);
  16.         int inRootPos = find(inorder, begin2, end2, preorder[begin1]);
  17.         int leftSize = inRootPos - begin2;
  19.         root.left = buildTree(preorder, begin1 + 1, begin1 + leftSize + 1, 
  20.                 inorder, begin2, begin2 + leftSize);
  21.         root.right = buildTree(preorder, begin1 + leftSize + 1, end1,
  22.                 inorder, inRootPos + 1, end2);
  24.         return root;
  25.     }
  26.     private static int find(int[] array, int begin, int end, int val) {
  27.         for (int i = begin; i < end; ++i) {
  28.             if (array[i] == val) return i;
  29.         }
  30.         return -1;
  31.     }
  32. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/binary-tree/construction/construct-binary-tree-from-preorder-and-inorder-traversal.html