提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

剑指offer No.4 重建二叉树（C++|Java版本）

JAVAC++二叉树 版本 Offer 重建
2023-06-13 09:13:26 时间

题目描述

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

图1 根据前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}重建的二叉树

二叉树结点的定义如下：

 struct BinaryTreeNode
 {
        int                    m_nValue;
        BinaryTreeNode＊       m_pLeft;
        BinaryTreeNode＊       m_pRight;
 };

在二叉树的前序遍历序列中，第一个数字总是树的根结点的值。但在中序遍历序列中，根结点的值在序列的中间，左子树的结点的值位于根结点的值的左边，而右子树的结点的值位于根结点的值的右边。因此我们需要扫描中序遍历序列，才能找到根结点的值。

如图2所示，前序遍历序列的第一个数字1就是根结点的值。扫描中序遍历序列，就能确定根结点的值的位置。根据中序遍历特点，在根结点的值1前面的3个数字都是左子树结点的值，位于1后面的数字都是右子树结点的值。

由于在中序遍历序列中，有 3 个数字是左子树结点的值，因此左子树总共有3 个左子结点。同样，在前序遍历的序列中，根结点后面的3 个数字就是 3 个左子树结点的值，再后面的所有数字都是右子树结点的值。这样我们就在前序遍历和中序遍历两个序列中，分别找到了左右子树对应的子序列。

图2 在二叉树的前序遍历和中序遍历的序列中确定根结点的值、左子树结点的值和右子树结点的值

既然我们已经分别找到了左、右子树的前序遍历序列和中序遍历序列，我们可以用同样的方法分别去构建左右子树。也就是说，接下来的事情可以用递归的方法去完成。在想清楚如何在前序遍历和中序遍历的序列中确定左、右子树的子序列之后，我们可以写出如下的递归代码

1、C++

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin)
    {
        if(pre.size() != vin.size())
            return NULL;
        int rootIndex=0;
        int size = pre.size();
        if(size==0){
            return NULL;
        }
        //查找根节点在先序遍历数组中的下标
        TreeNode *treeNode=new TreeNode(pre[0]);

        for(int i=0;i<size;i++) {
            //中序遍历数组中的第一个位置是根节点
            if(vin[i]==pre[0]) {
                rootIndex=i;
                break;
            }
        }
        //将先序的遍历结果分成两份，一份是左子树，一份是右子树
        int leftlength = rootIndex;
        int rightlength = size - 1 - rootIndex;
        vector<int> preLeft(leftlength),vinLeft(leftlength);;
        vector<int> preRight(rightlength),vinRight(rightlength);

        // 把左右子树填写好
        for(int i = 0; i < size; i++)
        {
            if(i < leftlength)
            {
                preLeft[i] = pre[i+1];
                vinLeft[i] = vin[i];
            }
            else if(i > leftlength)
            {
                preRight[i-leftlength-1] = pre[i];
                vinRight[i-leftlength-1] = vin[i];
            }
        }
        treeNode->left=reConstructBinaryTree(preLeft,vinLeft);
        treeNode->right= reConstructBinaryTree(preRight,vinRight);
        return treeNode;
    }
    void preVisit(TreeNode* treeNode){
        if(treeNode==NULL){
            return;
        }
        cout << treeNode->val << ",";
        preVisit(treeNode->left);
        preVisit(treeNode->right);
    }
    void midVisit(TreeNode* treeNode){
        if(treeNode==NULL){
            return;
        }
        midVisit(treeNode->left);
        cout << treeNode->val << ",";
        midVisit(treeNode->right);
    }
};

2、Java

package offer.reConstructBinaryTree;

public class Solution {
    //pre:先序 in:中序
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        TreeNode treeNode=new TreeNode(pre[0]);
        //查找根节点在先序遍历数组中的下标
        int rootIndex=0;
        for(int i=0;i<in.length;i++) {
            //中序遍历数组中的第一个位置是根节点
            if(in[i]==pre[0]) {
                rootIndex=i;
            }
        }
        //将先序的遍历结果分成两份，一份是左子树，一份是右子树
        int[] preLeft=new int[rootIndex];
        int[] preRight=new int[pre.length-rootIndex-1];
        for(int i=0;i<rootIndex;i++) {
            preLeft[i]=pre[i+1];
        }
        for(int i=0;i<pre.length-rootIndex-1;i++) {
            preRight[i]=pre[rootIndex+1+i];
        }
        //将中序的遍历的结果分为两份，一份是左子树，一份是右子树
        int[] midLeft=new int[rootIndex];
        int[] midRight=new int[in.length-rootIndex-1];
        for(int i=0;i<rootIndex;i++) {
            midLeft[i]=in[i];
        }
        for(int i=0;i<in.length-rootIndex-1;i++) {
            midRight[i]=in[rootIndex+i+1];
        }
        if(in.length>0&pre.length>0) {
            if(preLeft.length>0) {
                treeNode.left=reConstructBinaryTree(preLeft,midLeft);
            }
            if(preRight.length>0) {
                treeNode.right= reConstructBinaryTree(preRight,midRight);
            }
        }
        return treeNode;
    }
    public void preVisit(TreeNode treeNode){
        if(treeNode==null){
            return;
        }
        System.out.print(treeNode.val+",");
        preVisit(treeNode.left);
        preVisit(treeNode.right);
    }
    public void midVisit(TreeNode treeNode){
        if(treeNode==null){
            return;
        }
        midVisit(treeNode.left);
        System.out.print(treeNode.val+",");
        midVisit(treeNode.right);
    }
    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};
        Solution solution=new Solution();
        TreeNode treeNode=solution.reConstructBinaryTree(pre,in);
        solution.preVisit(treeNode);
        System.out.println();
        solution.midVisit(treeNode);
        System.out.println();
    }
}

相关文章