題目描述

根據(jù)一個(gè)樹的前序遍歷與中序遍歷構(gòu)造二叉樹。(假設(shè)樹中沒有重復(fù)的元素)。
105. 從前序與中序遍歷序列構(gòu)造二叉樹

解法1 遞歸

遞歸應(yīng)該是這道題最直接的想法，遞歸生成樹，需要節(jié)點(diǎn)值，節(jié)點(diǎn)的左孩子和右孩子，左右孩子可以遞歸生成。
根據(jù)前序遍歷序列和中序遍歷序列的特點(diǎn)，前序遍歷序列的第一個(gè)元素是根的值，接下來是左子樹和右子樹；中序遍歷先是左子樹、然后是根、最后是右子樹。
解決這道題第一步是確定根節(jié)點(diǎn)在中序遍歷的位置，這樣才好區(qū)分中序遍歷中那些屬于左子樹、那些屬于右子樹。我么知道根的值，可以通過一次循環(huán)查找到位置，但更推薦使用Hashmap，在之后的遞歸中，可以根據(jù)索引找到對應(yīng)的坐標(biāo)。
第二步構(gòu)建樹，根的值已經(jīng)知道，接下來就是找到左右節(jié)點(diǎn)。遞歸實(shí)現(xiàn)。

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;
    }
}

題目描述

根據(jù)一棵樹的中序遍歷與后序遍歷構(gòu)造二叉樹。（假設(shè)數(shù)中沒有重復(fù)的元素）。
106. 從中序與后序遍歷序列構(gòu)造二叉樹

解法1 遞歸

與上面一道題類似。確定根節(jié)點(diǎn)的值，其在后序遍歷的末尾。

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;
    }
}