剑指offer之重建二叉树

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

2.解题思路：我们知道，根据一个二叉树的前序遍历结果和中序遍历结果可以推导出这棵二叉树的结构；前序遍历：中左右；中序遍历：左中右；例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}；

1.先根据前序遍历找出根节点。前序遍历第一个数就是根节点案例中是1；

2. 再从中序遍历的序列中确定根节点的位置in[3]，将序列一分为二，根节点的左边是左子树，右边是右子树。案例中{4,7,2}是左子树的前序序列，{5,3,8,6}是右子树的中序序列。

3.然后从前序遍历的序列中依次拿出第二个数，第二个数为2，所以中序中的{4,7,2}，按2划分边界，{4,7}在左边所以左子树的节点就有{4,7}，右边没节点，所以以2为根结点的右子树为空。

4.依次执行2,3步骤就可以完成二叉树的重建。整个过程可以用递归实现。

3.代码

/**

 * Definition for binary tree

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

import java.util.Arrays;

public class Solution {

    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {

        if(pre.length==0||in.length==0){

            return null;

        }

        TreeNode result= new TreeNode(pre[0]);

        for (int i = 0; i < in.length; i++) {

            if (in[i] == pre[0]) {

                // 左子树，copyOfRange 函数包头不包尾（范围是左闭右开），

                result.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,i + 1), Arrays.copyOfRange(in, 0, i));

                // 右子树

                result.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));

                //结束

                break;

            }

        }

                      return result;

    }

}

巴特西

剑指offer之重建二叉树

最新文章

热门文章