7题目描述:

输入某二叉树的前序遍历和中序遍历的结果,请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

解析:

知识点:

前序遍历列表:
第一个元素永远是 【根节点 (root)】
中序遍历列表:
根节点 (root)【左边】的所有元素都在根节点的【左分支】,【右边】的所有元素都在根节点的【右分支】

算法思路:

通过【前序遍历列表】确定【根节点 (root)】
将【中序遍历列表】的节点分割成【左分支节点】和【右分支节点】
递归寻找【左分支节点】中的【根节点 (left child)】和 【右分支节点】中的【根节点 (right child)】

Java:

public TreeNode buildTree(int[] preorder, int[] inorder) {
        int length = preorder.length;
        if(length == 0) {
            return null;
        }
        int rootValue = preorder[0];
        int rootIndex = 0;
        for(int i = 0; i < length; i++) {
            if(inorder[i] == rootValue) {
                rootIndex = i;
                break;
            }
        }
        TreeNode root = new TreeNode(rootValue);
        root.left = buildTree(Arrays.copyOfRange(preorder, 1, rootIndex + 1),
        Arrays.copyOfRange(inorder, 0, rootIndex + 1));
        root.right = buildTree(Arrays.copyOfRange(preorder, rootIndex + 1, length),
        Arrays.copyOfRange(inorder, rootIndex + 1, length));
        return root;
    }

JavaScript:

var buildTree = function(preorder, inorder) {
    if(preorder.length === 0) {
        return null;
    }
    const tree = new TreeNode(preorder[0]);

    let inorderRootIndex = inorder.indexOf(tree.val);
    let preorderLeft = preorder.slice(1, inorderRootIndex + 1);
    let inorderLeft = inorder.slice(0, inorderRootIndex);
    tree.left = buildTree(preorderLeft, inorderLeft);

    let preorderRight = preorder.slice(inorderRootIndex + 1);
    let inorderRight = inorder.slice(inorderRootIndex + 1);
    tree.right = buildTree(preorderRight, inorderRight);

    return tree;
};

16题目描述:

实现 pow(x, n) ,即计算 x 的 n 次幂函数(即,xn)。不得使用库函数,同时不需要考虑大数问题。

解析:

1.快速幂

pow(2, 10)
pow(2 * 2, 5)
pow(2, 4) * 2
pow(2, 2) * pow(2, 2)
pow(2, 1) * pow(2, 1)

Java:

public double myPow(double x, int n) {
        if(n == 0) {
            return 1;
        }
        if(n == 1) {
            return x;
        }
        if(n == -1) {
            return 1 / x;
        }
        if(n % 2 != 0) {
            return x * myPow(x, n - 1);
        }
        return myPow(x * x, n / 2);
    }

JavaScript:

var myPow = function(x, n) {
    if(n === 0) {
        return 1;
    }
    if(n === 1) {
        return x;
    }
    if(n < 0) {
        return 1 / myPow(x, -n);
    }
    if(n % 2 !== 0) {
        return x * myPow(x, n - 1);
    }
    return myPow(x * x, n / 2);
};