LeetCode笔记整理2 从中序与前(后)序列构造二叉树

从中序与前(后)序列构造二叉树

遍历顺序

前序

• 先遍历根节点
• 随后递归遍历左子树
• 随后递归遍历右子树

特点:
第一个节点一定为树的根节点

中序

• 先递归遍历左子树
• 随后遍历根节点
• 最后递归遍历右子树

特点:

• 根节点左边为左子树
• 根节点右边为右子树

后序

• 先递归遍历左子树
• 随后递归遍历右子树
• 最后遍历根节点

特点:
最后一个节点一定为树的根节点

递归

只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到前序遍历的结果中，对上述形式中的所有左右括号进行定位。

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

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}
var buildTree = function(preorder, inorder) {
    if (inorder.length === 0){
        return null
    }
    var root = new TreeNode(preorder[0])
    var mid = inorder.indexOf(preorder[0])
    root.left = buildTree(preorder.slice(1, mid + 1), inorder.slice(0, mid))
    root.right = buildTree(preorder.slice(mid+1), inorder.slice(mid+1))
    return root
};

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

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

function TreeNode(val){
    this.val = val
    this.left = this.right = null;
}
var buildTree = function(inorder, postorder) {
    if(postorder.length === 0)
        return null
    var val = postorder[postorder.length - 1]
    var root = new TreeNode(val)
    var mid = inorder.indexOf(val)
    root.left = buildTree(inorder.slice(0, mid), postorder.slice(0, mid))
    root.right = buildTree(inorder.slice(mid+1), postorder.slice(mid, postorder.length - 1))
    return root
};