从前序与中序遍历序列构造二叉树

题目链接

题解：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)

执行结果: