剑指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 条评论
登录 后参与评论

相关文章

来自专栏韦弦的偶尔分享

Swift 验证二叉搜索树- LeetCode

对isValidBSTUtil(node.left, min, node.val) && isValidBSTUtil(node.right, node.val...

1564
来自专栏LeetCode

LeetCode 112&113&437 Path Sum I&II&III

Given a binary tree and a sum, determine if the tree has a root-to-leaf path suc...

1126
来自专栏mathor

LeetCode144.二叉树的前序遍历&94.二叉树的中序遍历&145.二叉树的后序遍历

 后序遍历的非递归代码得说一下,首先后序遍历得顺序是左右中,我们知道先序遍历的压栈顺序是先压右再压左,这样出来的顺序就是中左右,如果把先序遍历的压栈顺序稍微变一...

3753
来自专栏Jack-Cui

501.Find Mode in Binary Search Tree(Tree-Easy)

Given a binary search tree (BST) with duplicates, find all the mode(s) (the most...

2186
来自专栏算法修养

LeetCode 102. Binary Tree Level Order Traversal

1484
来自专栏书山有路勤为径

二叉树转链表

给定一个二叉树,将该二叉树 就地(in-place)转换为单链表。单链表中节点顺序 为二叉树前序遍历顺序。(不额外开辟存储空间) LeetCode 114. ...

622
来自专栏赵俊的Java专栏

二叉树层序遍历为二维数组

1873
来自专栏desperate633

LintCode 验证二叉查找树题目分析代码

2 / 1 4 / 3 5 上述这棵二叉树序列化为 {2,1,4,#,#,3,5}.

912
来自专栏Jack-Cui

111.Minimum Depth of Binary Tree(Tree-Easy)

Given a binary tree, find its minimum depth. The minimum depth is the number of ...

2079
来自专栏LeetCode

LeetCode 872. Leaf-Similar Trees

Consider all the leaves of a binary tree.  From left to right order, the values ...

1330

扫码关注云+社区