LCR124

问题描述

某二叉树的先序遍历结果记录于整数数组 preorder，它的中序遍历结果记录于整数数组 inorder。请根据 preorder 和 inorder 的提示构造出这棵二叉树并返回其根节点。

注意：preorder 和 inorder 中均不含重复数字。

示例 1：

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]

输出: [-1]

提示:

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• inorder 均出现在 preorder
• preorder 保证 为二叉树的前序遍历序列
• inorder 保证 为二叉树的中序遍历序列

解答

分治，先序遍历和中序遍历可以分成几个小的，最终分成最小的部分重构。

Definition for a binary tree node.
public class TreeNode {
   int val;
   TreeNode left;
   TreeNode right;
   TreeNode() {}
   TreeNode(int val) { this.val = val; }
   TreeNode(int val, TreeNode left, TreeNode right) {
      this.val = val;
      this.left = left;
      this.right = right;
   }
}

class Solution {
   public TreeNode deduceTree(int[] preorder, int[] inorder) {
       if (preorder.length==0) return null;
       TreeNode root = new TreeNode(preorder[0]);
       findroot(preorder, inorder, root);
       return root;
   }

   public TreeNode findroot(int[] preorder, int[] inorder, TreeNode root) {
       root.val = preorder[0];
       int i=0;
       while(inorder[i]!=preorder[0]) i++;
       if(i!=0){
           int[] preorder_left = Arrays.copyOfRange(preorder,1,i+1);
           int[] inorder_left = Arrays.copyOfRange(inorder,0,i);
           root.left = new TreeNode();
           findroot(preorder_left,inorder_left,root.left);
       }
       if(i!=preorder.length-1){
           int[] preorder_right = Arrays.copyOfRange(preorder,i+1,preorder.length);
           int[] inorder_right = Arrays.copyOfRange(inorder,i+1,inorder.length);
           root.right = new TreeNode();
           findroot(preorder_right,inorder_right,root.right);
       }
       return root;
   }
}