输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如,给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:
3
/ \
9 20
/ \
15 7
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
//使用递归的思想 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { if (preorder.length == 0){ return null; } TreeNode treeNode = new TreeNode(preorder[0]); if(preorder.length == 1){ return treeNode; } List<Integer> preorderLeftList = new ArrayList<Integer>(); List<Integer> preorderRightList = new ArrayList<Integer>(); List<Integer> inorderLeftList = new ArrayList<Integer>(); List<Integer> inorderRightList = new ArrayList<Integer>(); int inorderLen = inorder.length; for (int i=0; i<inorderLen; i++){ if(inorder[i] == preorder[0]){ break; }else{ inorderLeftList.add(inorder[i]); } } for(int j=inorderLeftList.size()+1; j<inorderLen; j++){ inorderRightList.add(inorder[j]); } for (int k=1; k<=inorderLeftList.size(); k++){ preorderLeftList.add(preorder[k]); } for (int m=inorderLeftList.size()+1; m<preorder.length; m++){ preorderRightList.add(preorder[m]); } int[] preLeftArr = new int[preorderLeftList.size()]; int[] inoderLeftArr = new int[inorderLeftList.size()]; int[] preRightArr = new int[preorderRightList.size()]; int[] inoderRightArr = new int[inorderRightList.size()]; preLeftArr = listToInt(preLeftArr,preorderLeftList); preRightArr = listToInt(preRightArr,preorderRightList); inoderLeftArr = listToInt(inoderLeftArr,inorderLeftList); inoderRightArr = listToInt(inoderRightArr,inorderRightList); TreeNode leftTreeNode = buildTree(preLeftArr,inoderLeftArr); TreeNode rightTreeNode = buildTree(preRightArr,inoderRightArr); treeNode.left = leftTreeNode; treeNode.right = rightTreeNode; return treeNode; } private int[] listToInt(int[] arr, List<Integer> list){ for (int i=0; i<list.size(); i++){ arr[i] = list.get(i); } return arr; } }
原文:https://www.cnblogs.com/zldmy/p/12393098.html