题目

image.png

思路

  • 根据前序遍历来构造二叉树，根据中序遍历来限定左右子树的范围

    代码

    1.    public TreeNode buildTree(int[] preorder, int[] inorder) {
    2.       return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length);
    3.   }
    5.   private TreeNode buildTree(int[] preorder, int pStart, int pEnd, int[] inorder, 
    6.           int iStart, int iEnd) {
    7.       if (pStart > pEnd) return null;
    8.       TreeNode root = new TreeNode(preorder[pStart]);
    9.       int i, range;
    10.       for (i = iStart; i < iEnd; i++) {
    11.           if (inorder[i] == preorder[pStart]) break;
    12.       }
    13.       range = i - iStart;
    14.       root.left = buildTree(preorder, pStart + 1, pStart + range, inorder, iStart, i);
    15.       root.right = buildTree(preorder, pStart + range + 1, pEnd, inorder, i + 1, iEnd);
    16.       return root;
    17.   }

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