剑指offer--重建二叉树

AI那点小事

发布于 2020-04-18 20:21:37

2540

发布于 2020-04-18 20:21:37

文章被收录于专栏：AI那点小事AI那点小事

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

思路：先来分析一下前序遍历和中序遍历得到的结果，

前序遍历第一位是根节点；中序遍历中，根节点左边的是根节点的左子树，右边是根节点的右子树。

例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}。

首先，根节点是{ 1 }；左子树是：前序{ 2,4,7 } ，中序{ 4,7,2 }；右子树是：前序{ 3,5,6,8 } ，中序{ 5,3,8,6 }；

这时，如果我们把左子树和右子树分别作为新的二叉树，则可以求出其根节点，左子树和右子树。

这样，一直用这个方式，就可以实现重建二叉树。

Java代码：

/**
 * Definition for binary tree
 public class TreeNode {
      int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
  }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int prestart ,int preend,int [] pre,int instart,int inend, int [] in){
        TreeNode tree = new TreeNode(pre[prestart]);
        tree.left = null;
        tree.right = null;
        if ( prestart == preend && instart == inend){
            return tree;
        }

        int root = 0;
        for (root = instart ; root < inend ; root++){
            if ( pre[prestart] == in[root]){
                break;
            }
        }

        int leftlength = root - instart;
        int rightlength = inend - root;
        if ( leftlength > 0){
            tree.left = reConstructBinaryTree(prestart+1, prestart+leftlength , pre, instart, root-1, in);
        }
        if ( rightlength > 0){
            tree.right = reConstructBinaryTree(prestart+1+leftlength, preend, pre, root+1, inend, in);
        }

        return tree;
    }

    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if ( pre == null || in == null){
            return null;
        }
        TreeNode root = reConstructBinaryTree(0, pre.length-1, pre, 0, in.length-1, in);
        return root;
    }
}

c++代码如下：

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
    public:
        TreeNode* Build(int* Pre,int* Vin ,int len){
            if(!Pre || !Vin || len < 0){
                return NULL;
            }   
            int root_index = 0;
            for(root_index = 0 ; root_index < len ; root_index++){
                if(Vin[root_index] == Pre[0]){
                    break;
                }
            }
            if(root_index == len){
                return NULL;
            }
            TreeNode *root;
            root = new TreeNode(Pre[0]);
            root->left = root->right = NULL; 
            if(root_index > 0){
                root->left = Build(Pre+1,Vin,root_index);
            }
            if(len-root_index-1 > 0){
                root->right = Build(Pre+root_index+1,Vin+root_index+1,len-root_index-1);
            }
            return root;
        }

        TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
            int len = pre.size();
            int *Pre,*Vin;
            Pre = new int[len];
            Vin = new int[len];
            for(int i = 0 ; i < len ; i++){
                Pre[i] = pre[i];
                Vin[i] = vin[i];
            }
            TreeNode *root = this->Build(Pre,Vin,len);
            return root;
        }
};