【剑指Offer】- 重建二叉树[Java版]

迷南。 2022-05-22 01:55 161阅读 0赞

**题目描述**  
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序遍历序列\{4,7,2,1,5,3,8,6\}，则重建二叉树并返回。

/** * Created by Joe on 2018/6/6 */
    /** * Created by Joe on 2018/6/6 */
    public class Main { 
        public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
            // 如果长度为1，则返回节点
            if (pre.length == 1) {
                return new TreeNode(pre[0]);
            }
    
            // 如果长度大于1，则进行左右子树的切分
            if (pre.length > 1) {
                // 查找中序遍历中的根节点位置，用于划分左右子树
                int rootIndex = findIndex(pre[0], in);
                TreeNode node = new TreeNode(pre[0]);
    
    
                // 切分左子树
                int leftLength = rootIndex;
                int[] preLeft = new int[leftLength];
                System.arraycopy(pre, 1, preLeft, 0, leftLength);
                int[] inLeft = new int[leftLength];
                System.arraycopy(in, 0, inLeft, 0, leftLength);
                // 继续递归左子树
                node.left = reConstructBinaryTree(preLeft, inLeft);
    
                // 切分右子树
                int rightLength = in.length - 1 - rootIndex;
                int[] preRight = new int[rightLength];
                System.arraycopy(pre, 1 + leftLength, preRight,0, rightLength);
                int[] inRight = new int[rightLength];
                System.arraycopy(in, rootIndex + 1, inRight, 0, rightLength);
                // 继续递归右子树
                node.right = reConstructBinaryTree(preRight, inRight);
    
                return node;
            }
            return null;
        }
    
        public static void preTravle(TreeNode node) {
            if (node != null) {
                System.out.print(node.val + ",");
                preTravle(node.left);
                preTravle(node.right);
            }
        }
    
        public int findIndex(int val, int[] arr) {
            for (int i = 0; i < arr.length; i++) {
                if (val == arr[i]) {
                    return i;
                }
            }
            return -1;
        }
    
        public static void main(String[] args) {
            TreeNode root = new Main().reConstructBinaryTree(
                    new int[] {
       1,2,4,3,5,6},
                    new int[] {
       4,2,1,5,3,6}
            );
    
            preTravle(root);
        }
    }
    
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    
        TreeNode(int x) {
            val = x;
        }
    }