专栏首页Echo is learning剑指offer04--重建二叉树

剑指offer04--重建二叉树

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

思路:

设前序遍历序列为pre,中序遍历序列为in,则易知:

1)root = pre[0];

2)in[ ] 中 root 的位置(索引)将 in[ ] 分成了root 的左子树和右子树两个部分;

如图所示:先序中的第一个元素就是树的根root 1,在中序中这个根 1 将序列分为了左(4,7,2)、右(5,3,8,6)子树;

递归的看,左子树也有先序(2,4,7)和中序(4,7,2)两个序列,右子树同理;

  • c++代码:
 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
13          // 递归退出条件
14         if(pre.size() == 1) {
15             TreeNode *root = new TreeNode(pre[0]);
16             return root;
17         }
18          // 递归退出条件
19         if(pre.size() == 0) {
20             return NULL;
21         }
22         // 中序中root的位置 
23         int i;
24         for(i = 0; i < vin.size(); i++)
25             if(vin[i] == pre[0])
26                 break;
27          
28         vector<int> inLeft;
29         vector<int> preLeft;
30         vector<int> inRight;
31         vector<int> preRight;
32         // 左子树的先序和中序序列
33         for(int j = 0; j < i; j++) {
34             inLeft.push_back(vin[j]);
35             preLeft.push_back(pre[j+1]);
36         }
37         // 右子树的先序和中序序列 
38         for(int j = 0; j < vin.size()-i-1; j++) {
39             inRight.push_back(vin[j+i+1]);
40             preRight.push_back(pre[j+i+1]);
41         }
42              
43         TreeNode *root = new TreeNode(pre[0]);
44         root->left = reConstructBinaryTree(preLeft, inLeft);
45         root->right = reConstructBinaryTree(preRight, inRight);
46          
47         return root;
48     }
49 };
  •  java代码:
 1 /**
 2  * Definition for binary tree
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
12 
13         // 递归退出条件
14         if(pre.length == 1) {
15             TreeNode root = new TreeNode(pre[0]);
16             return root;
17         }
18 
19         // 递归退出条件
20         if(pre.length == 0)
21             return null;
22          
23         // 中序中root的索引
24         int i;
25         for(i = 0; i < in.length; i++)
26             if(in[i] == pre[0])
27                 break;
28          
29         int [] inLeft = new int[i];
30         int [] preLeft = new int[i];
31         int [] inRight = new int[in.length-i-1];
32         int [] preRight = new int[in.length-i-1];
33          
34         // 左子树的中序和先序序列
35         for(int j = 0; j < i; j++) {
36             inLeft[j] = in[j];
37             preLeft[j] = pre[j+1];
38         }
39          
40         // 右子树的中序和先序序列
41         for(int j = 0; j < in.length-i-1; j++) {
42             inRight[j] =  in[j+i+1];
43             preRight[j] = pre[j+i+1];
44         }
45              
46         TreeNode root = new TreeNode(pre[0]);
47         root.left = reConstructBinaryTree(preLeft, inLeft);
48         root.right = reConstructBinaryTree(preRight, inRight);
49          
50         return root;
51     }
52 }    

 算法的改进:

  • 这种做法每次递归都需要开辟4个数组来保存左、右子树的先、中序列,占用了很多的空间;
  • 考虑用把函数的形参换成数组的起始位置,来代替每次传入数组;

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 简单爬虫 -- 以爬取NASA AOD数据(TIFF文件)为例

    Echo_fy
  • machine learning 之 Neural Network 2

    Echo_fy
  • python 之 列表list && 元组tuple

    Echo_fy
  • 如何为ABAP类创建隐式增强

    Jerry Wang
  • Tree

    Little Valentine liked playing with binary trees very much. Her favorite game wa...

    书童小二
  • 【Leetcode】104. 二叉树的最大深度

    求最大深度,和深度相关,我们很容易想到用层序遍历。每遍历一层,就深度加1, 怎么记录是第几层我们之前的文章中讲过了。

    Leetcode名企之路
  • 承接上文

    前置通知[Before advice]:在连接点前面执行,前置通知不会影响连接点的执行,除非此处抛出异常。 

    小勇DW3
  • Leetcode#104. Maximum Depth of Binary Tree(二叉树的最大深度)

    武培轩
  • 美团面试题:如何分析差评原因?

    需要分析导致分析差评的原因是什么,并给出改善方案。可以使用《猴子数据分析》里第6关讲过的分析方法,和第7-8关的如何用数据分析解决问题的框架来完成。

    猴子聊数据分析
  • P1146 硬币翻转

    题目描述 在桌面上有一排硬币,共N枚,每一枚硬币均为正面朝上。现在要把所有的硬币翻转成反面朝上,规则是每次可翻转任意N-1枚硬币(正面向上的被翻转为反面向上,反...

    attack

扫码关注云+社区

领取腾讯云代金券