剑指offer-07

剑指offer-07 重建二叉树

题目

结果

普通版

改进版

代码

普通版

public class LeetCode {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] preorder = new int[]{3, 9, 20, 15, 7};
        int[] inorder = new int[]{9, 3, 15, 20, 7};
        TreeNode root = solution.buildTree(preorder, inorder);
    }
}

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 递归终止的情况
        int len = preorder.length;
        if (len == 0) {
            return null;
        }

        // 构造树的根节点
        TreeNode tree = new TreeNode(preorder[0]);

        // 找到根节点在中序遍历中的位置
        int root = 0;
        for (int i = 0; i < len; i++) {
            if (inorder[i] == preorder[0]) {
                root = i;
                break;
            }
        }

        // 初始化左右子树的先序和中序遍历结果
        int[] leftPre = new int[root];
        int[] rightPre = new int[len - root - 1];
        int[] leftIn = new int[root];
        int[] rightIn = new int[len - root - 1];

        // 构造左子树的先序和中序遍历结果
        for (int i = 0; i < root; i++) {
            leftPre[i] = preorder[i + 1];
            leftIn[i] = inorder[i];
        }

        // 构造右子树的先序和中序遍历结果
        for (int i = 0; i < rightPre.length; i++) {
            rightPre[i] = preorder[root + i + 1];
            rightIn[i] = inorder[root + i + 1];
        }

        // 递归地构造左右子树
        tree.left = buildTree(leftPre, leftIn);
        tree.right = buildTree(rightPre, rightIn);
        return tree;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

改进版

package eternal.fire.java;

import java.util.HashMap;
import java.util.Map;

public class LeetCode {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] preorder = new int[]{1, 2, 3};
        int[] inorder = new int[]{3, 2, 1};
        TreeNode root = solution.buildTree(preorder, inorder);
    }
}

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 特殊情况
        if (preorder.length == 0) {
            return null;
        }
        // map存储根节点再inorder出现的位置
        Map<Integer, Integer> rootIndex = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            rootIndex.put(inorder[i], i);
        }

        return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, rootIndex);
    }

    /**
     * @param preorder  先序遍历数组
     * @param preBegin  先序遍历数组的起点
     * @param preEnd    先序遍历数组的终点
     * @param inorder   中序遍历数组
     * @param inBegin   中序遍历数组的起点
     * @param inEnd     中序遍历数组的终点
     * @param rootIndex 根节点在inorder中出现的位置
     * @return 构造好的二叉树
     */
    private TreeNode buildTree(int[] preorder, int preBegin, int preEnd, int[] inorder, int inBegin, int inEnd, Map<Integer, Integer> rootIndex) {
        if (preBegin > preEnd) {
            return null;
        }

        // 构造根节点
        TreeNode treeRoot = new TreeNode(preorder[preBegin]);

        if (preBegin == preEnd) {
            return treeRoot;
        }

        // 根节点的在中序遍历中的位置
        int root = rootIndex.get(preorder[preBegin]);

        // 左右子树的元素个数
        int leftLen = root - inBegin;

        treeRoot.left = buildTree(preorder, preBegin + 1, preBegin + leftLen, inorder, inBegin, root - 1, rootIndex);
        treeRoot.right = buildTree(preorder, preBegin + leftLen + 1, preEnd, inorder, root + 1, inEnd, rootIndex);
        return treeRoot;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

改进版用一个map存储根元素在中序遍历序列中出现的位置，避免了每次都要去找根节点，节约了时间。

改进版只使用了原来的数组，没有new新的数组，节约了空间和时间。

这题真做吐了。