( Leetcode 刷题)从前序与中序遍历序列构造二叉树、从中序与后序遍历序列构造二叉树

题目描述

根据一个树的前序遍历与中序遍历构造二叉树。(假设树中没有重复的元素)。
105. 从前序与中序遍历序列构造二叉树

解法1 递归

递归应该是这道题最直接的想法，递归生成树，需要节点值，节点的左孩子和右孩子，左右孩子可以递归生成。
根据前序遍历序列和中序遍历序列的特点，前序遍历序列的第一个元素是根的值，接下来是左子树和右子树；中序遍历先是左子树、然后是根、最后是右子树。
解决这道题第一步是确定根节点在中序遍历的位置，这样才好区分中序遍历中那些属于左子树、那些属于右子树。我么知道根的值，可以通过一次循环查找到位置，但更推荐使用Hashmap，在之后的递归中，可以根据索引找到对应的坐标。
第二步构建树，根的值已经知道，接下来就是找到左右节点。递归实现。

B66C4FD43A71DEE0FFBD69769B31B7A3.png

/**
 * 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) {
        HashMap<Integer, Integer> hashmap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            hashmap.put(inorder[i], i);
        }
        return buildTreeHelper(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1, hashmap);
    }

    public TreeNode buildTreeHelper(int[] preorder, int[] inorder, int pstart, int pend, int istart, int iend, HashMap<Integer, Integer> hashmap) {
        //左孩子或右孩子为空
        if (pstart > pend || istart > iend) {
            return null;
        }
        int rootval = preorder[pstart];
        TreeNode root = new TreeNode(rootval);
        int iroot = hashmap.get(rootval);
        //注意范围，pstart + 1 到pstart + iroot - istart 属于前序中的左子树范围，istart 到 iroot - 1 属于中序中的左子树
        root.left = buildTreeHelper(preorder, inorder, pstart + 1, pstart + iroot - istart, istart, iroot - 1, hashmap);
        //同理， pstart + iroot - istart + 1 到 pend 属于前序中的右子树范围， iroot + 1到 iend 属于中序中的右子树
        root.right = buildTreeHelper(preorder, inorder, pstart + iroot - istart + 1, pend, iroot + 1, iend, hashmap);
        return root;
    }
}

题目描述

根据一棵树的中序遍历与后序遍历构造二叉树。（假设数中没有重复的元素）。
106. 从中序与后序遍历序列构造二叉树

解法1 递归

与上面一道题类似。确定根节点的值，其在后序遍历的末尾。

6C2D0B5C744FCA7E5854592957D27910.png

/**
 * 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) {
        HashMap<Integer, Integer> hashmap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            hashmap.put(inorder[i], i);
        }
        return buildTree(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1, hashmap);
    }

    public TreeNode buildTree(int[] inorder, int[] postorder, int istart, int iend, int pstart, int pend, HashMap<Integer, Integer> hashmap) {
        if (pstart > pend || istart > iend) {
            return null;
        }
        int rootval = postorder[pend];
        TreeNode root = new TreeNode(rootval);
        int iroot = hashmap.get(rootval);
        root.left = buildTree(inorder, postorder, istart, iroot - 1, pstart, iroot + pstart - istart - 1, hashmap);
        root.right = buildTree(inorder, postorder, iroot + 1, iend, iroot + pstart - istart, pend - 1, hashmap);
        return root;
    }
}