《中英双解》leetCode Construct Binary Tree from Inorder and Postorder Traversal(从中序到后序遍历序列构造二叉树)
Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.
Example 1:
Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]
Example 2:Input: inorder = [-1], postorder = [-1]
Output: [-1]
Constraints:
1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder and postorder consist of unique values.
Each value of postorder also appears in inorder.
inorder is guaranteed to be the inorder traversal of the tree.
postorder is guaranteed to be the postorder traversal of the tree/** * 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 buildTree(int[] inorder, int[] postorder) { // int inLength = inorder.length; // int postLength = postorder.length; // if(inLength != postLength){ // throw new RuntimeException("error input data"); // } // Map<Integer,Integer> map = new HashMap<>(inLength); // for(int i = 0 ;i < inLength;i++){ // map.put(inorder[i],i); // } // return buildTree(map,0,inLength - 1,postorder,0,postLength - 1); // } // public TreeNode buildTree(Map<Integer,Integer> map,int inLeft,int inRight,int[] postorder,int postLeft,int postRight){ // if(inLeft > postLeft || postLeft > inLeft){ // return null; // } // int rootValue = postorder[postRight]; // TreeNode root = new TreeNode(rootValue); // int pIndex = map.get(rootValue); // root.left = buildTree(map,inLeft,pIndex-inLeft + postLeft - 1,postorder,postLeft,pIndex); // root.right = buildTree(map,pIndex + 1,inRight,postorder,pIndex - inLeft + postLeft + 1,postRight - 1); // return root; // } // } class Solution{ public TreeNode buildTree(int[] inorder, int[] postorder) { int i_len = inorder.length; int p_len = postorder.length; if(i_len == 0 || p_len == 0){ return null; } //通过后序序列,查找子树的根节点 int root_val = postorder[p_len - 1]; //构造根节点 TreeNode root = new TreeNode(root_val); //遍历中序序列,确定根结点在中序序列中的位置,从而确定左右子树 int k = 0; for (int i = 0; i < i_len; i++) { if(root_val == inorder[i]){ k = i; break; } } //分割左右子树,分别创建左右子树的中序、后序序列 int[] left_in = Arrays.copyOfRange(inorder, 0, k); int[] left_post = Arrays.copyOfRange(postorder, 0, k); root.left = buildTree(left_in,left_post); int[] right_in = Arrays.copyOfRange(inorder, k + 1, i_len); int[] right_post = Arrays.copyOfRange(postorder, k, p_len - 1); root.right = buildTree(right_in,right_post); return root; } }.我不明白我注释掉的代码为什么会超时,有大佬希望解答一下。
更多推荐
所有评论(0)