剑指offer--重建二叉树---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; } };

---来自腾讯云社区的---AI那点小事