从前序与中序遍历序列构造二叉树
题解：recursion
针对如上的二叉树：
前序遍历的结果为：
1 2 4 5 3 6 7
中序遍历的结果为:
4 2 5 1 6 3 7
规律如下：
前序遍历的第一个节点为头节点
-
在中序遍历的结果中，头节点左边的节点在左子树，头节点右边的节点在右子树
可以理解为：
这样我们就自然而然联想到了递归
代码如下：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTree(preorder,0,preorder.length - 1,inorder,0,inorder.length - 1);
}
private TreeNode buildTree(int[] preorder,int preStart,int preEnd,int[] inorder,int inStart,int inEnd){
if(preStart > preEnd || inStart > inEnd){
return null;
}
TreeNode head = new TreeNode(preorder[preStart]);
for(int i = inStart;i <= inEnd;i++){
if(inorder[i] == preorder[preStart]){
head.left = buildTree(preorder,preStart + 1,preStart + i - inStart,inorder,inStart,i - 1);
head.right = buildTree(preorder,preStart + i - inStart + 1,preEnd,inorder,i + 1,inEnd);
}
}
return head;
}
}
时间复杂度：O(N)
使用master公式求解：
master公式：T(N) = a*T(N/b) + O(N^d)
1) log(b,a) > d -> 复杂度为O(N^log(b,a))
2) log(b,a) = d -> 复杂度为O(N^d * logN)
3) log(b,a) < d -> 复杂度为O(N^d)
b代表的含义是递归分解成了几个子过程，a代表的含义是一次递归子过程执行了几次，O(N^d)表示除去递归外，额外需要的过程的时间复杂度。
本题中 a = 2,b = 2,d = 0
满足公式1，所以其时间复杂度为：O(Nlogb(a)) = O(N)
额外空间复杂度:O(N)
使用递归栈来存储整棵树，需要O(N)的额外空间
执行结果：
从中序与后序遍历序列构造二叉树
题解：recursion
思路和上一题的思路是完全一致的，这里面就不重复解释了，代码如下：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
// post-order
return buildTree(postorder,0,postorder.length - 1,inorder,0,inorder.length - 1);
}
private TreeNode buildTree(int[] postorder,int postStart,int postEnd,int[] inorder,int inStart,int inEnd){
if(inStart > inEnd || postStart > postEnd){
return null;
}
TreeNode head = new TreeNode(postorder[postEnd]);
for(int i = inStart;i <= inEnd;i++){
if(inorder[i] == postorder[postEnd]){
head.left = buildTree(postorder,postStart,postStart + i - inStart - 1,inorder,inStart,i - 1);
head.right = buildTree(postorder,postStart + i - inStart,postEnd - 1,inorder,i + 1,inEnd);
}
}
return head;
}
}
时间复杂度：O(N)
额外空间复杂度：O(N)
执行结果:
