剑指 Offer 07. 重建二叉树 & 16. 数值的整数次方

7题目描述：

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

解析：

知识点：

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

算法思路：

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

Java:

class Solution {
    int[] preorder;
    HashMap<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for(int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return recur(0, 0, inorder.length - 1);
    }
    TreeNode recur(int root, int left, int right) {
        if(left > right) {
            return null;
        }
        TreeNode node = new TreeNode(preorder[root]);
        int i = map.get(preorder[root]);
        node.left = recur(root + 1, left, i - 1);
        node.right = recur(root + i - left + 1, i + 1, right);
        return node;
    }
}

JavaScript:

var buildTree = function(preorder, inorder) {
    if(preorder.length === 0) {
        return null;
    }
    let node = new TreeNode(preorder[0]);
    let nodeIndex = inorder.findIndex(i => i == preorder[0]);
    node.left = buildTree(preorder.slice(1, nodeIndex + 1), inorder.slice(0, nodeIndex));
    node.right = buildTree(preorder.slice(nodeIndex + 1), inorder.slice(nodeIndex + 1));
    return node;
};

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 / myPow(x, -n);
        }
        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);
};