重建二叉树

题目来源：牛客网--重建二叉树

题目描述

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

概念引入

          A
        /   \
       /     \ 
     B         C
    / \       / \
   /   \     /   \
  D     E   F     G
  
前序遍历：根左右  A B D E C F G
中序遍历：左根右  D B E A F C G
后序遍历：左右根  D E B F G C A

解题思路

规律

1. 前序遍历的第一个数字肯定是一个节点 设为node
2. 在中序遍历中找到这个节点在数组中的下标 index，
3. index 左边的数字是 node 的左子树部分；
4. index 右边的数字是 node 的右子树部分。

所以，每次递归，只需要在中序遍历中，找到与前序遍历第一个数字相等的数字的位置，
然后对其左右的数字进行截取，重复上边的规律。

举例说明：

 前序遍历：pre = {1,2,4,7,3,5,6,8}
 中序遍历：in = {4,7,2,1,5,3,8,6}
    1、把 pre[0] 设为节点，root。
    2、在 in 中寻找 pre[0] 的位置，即 1 的下标，并把下标值赋值给 index。
    3、在 in 中，1 左边的数字，肯定是 root 的左子树部分；截取得到新数组 {4,7,2}；在 pre 中截取同样长度的数组 {2,4,7}。
    4、在 in 中，1 右边的数字，肯定是 root 的右子树部分；截取得到新数组 {5,3,8,6}；在 pre 中截取同样长度的数组 {3,5,6,8}

提交代码

// 我的方法名和牛客官方有出入
public static TreeNode refactoringBinaryTree(int[] pre, int[] in) {
    // 把前序遍历的第一个数设置为节点
    TreeNode root = new TreeNode(pre[0]);
    // 记录节点下标
    int index = 0;
    // 在中序遍历中寻找 与前序遍历第一个数相同的数字
    // 把下标值赋值给 index
    for (int i = 0; i < in.length; i++) {
        if (in[i] == pre[0]) {
            index = i;
            break;
        }
    }
    // 递归添加左节点
    if (index > 0) {
        root.left = refactoringBinaryTree(Arrays.copyOfRange(pre, 1, index + 1), 
                Arrays.copyOfRange(in, 0, index));
    }
    // 递归添加右节点
    if (index < in.length - 1) {
        root.right = refactoringBinaryTree(Arrays.copyOfRange(pre, index + 1, pre.length), 
                Arrays.copyOfRange(in, index + 1, in.length));
    }
    
    return root;
}

本地测试代码

package n_7_25;

import java.util.Arrays;

public class RefactoringBinaryTree {

    public static void main(String[] args) {
        int[] pre = {1,2,4,7,3,5,6,8};
        int[] in = {4,7,2,1,5,3,8,6};
        TreeNode root = refactoringBinaryTree(pre, in);
        output(root);
    }

    /**
     * 重构二叉树
     * 前序遍历的第一个数字肯定是一个节点 设为node
     * 在中序遍历中找到这个节点在数组中的下标 index，
     * index 左边的数字是 node 的左子树部分；
     * index 右边的数字是 node 的右子树部分。
     * @param pre
     * @param in
     */
    public static TreeNode refactoringBinaryTree(int[] pre, int[] in) {
        // 前序遍历的第一个数肯定是一个节点
        TreeNode root = new TreeNode(pre[0]);
        // 记录下标
        int index = 0;
        // 在中序遍历中寻找 与前序遍历第一个数相同的数字
        // 即 寻找节点在中序遍历中的下标
        for (int i = 0; i < in.length; i++) {
            if (in[i] == pre[0]) {
                index = i;
                break;
            }
        }
        // 递归添加左节点
        if (index > 0) {
            root.left = refactoringBinaryTree(Arrays.copyOfRange(pre, 1, index + 1), 
                    Arrays.copyOfRange(in, 0, index));
        }
        // 递归添加右节点
        if (index < in.length - 1) {
            root.right = refactoringBinaryTree(Arrays.copyOfRange(pre, index + 1, pre.length), 
                    Arrays.copyOfRange(in, index + 1, in.length));
        }
        
        return root;
    }
    
    
    // 输出函数 前序遍历（根节点最先，然后同级先左后右）
    static void output(TreeNode root) {
        System.out.print(root.value + "   ");
        if (root.left != null) {
            output(root.left);
        }
        if (root.right != null) {
            output(root.right);
        }
    }
}


// 二叉树
class TreeNode {
    int value;
    TreeNode left = null;
    TreeNode right = null;
    
    public TreeNode(int value) {
        this.value = value;
    }
}