算法-数组构建二叉树

1. leetcode105 从前序与中序遍历序列构建二叉树

1.1 思路

这种题思路很统一，掌握了之后很好下手，分为以下步骤：

1. 根据题目要求在数组中找到要构建的二叉树的根节点的值
2. 根据这个值构建一个根节点
3. 通过indexOf找出该值在数组中的位置下标
4. 根据该下标划分左右子树两个数组，重点是要把根节点排除在外
5. 递归操作，一般都是这样的：

root.left = buildTree(划分好之后的左边数组)
root.right = buildTree(划分好之后的右边数组)

比如这题，根节点显然要通过前序遍历的数组找到，因为前序遍历数组的第一个元素肯定是根节点，找出来后进行递归操作即可。

1.2 代码

var buildTree = function(preorder, inorder) {
    if(!preorder.length) return null;
    let rootVal = preorder.shift();
    let root = new TreeNode(rootVal);
    let cutIndex = inorder.indexOf(rootVal);

    let leftPreOrder = preorder.slice(0 , cutIndex);
    let rightPreOrder = preorder.slice(cutIndex);

    let leftInOrder = inorder.slice(0 , cutIndex);
    let rightInOrder = inorder.slice(cutIndex + 1);

    root.left = buildTree(leftPreOrder , leftInOrder);
    root.right = buildTree(rightPreOrder , rightInOrder);

    return root;
};

leetcode106和这题基本一模一样，除了根节点需要通过后序遍历数组pop出，因此不再赘述。

2. leetcode654 最大二叉树

2.1 思路

和上面那题区别在于找根节点的思路不同，这里题目要求以数组中的最大值作为根节点，找出来后别的步骤都是一样的，直接看代码。

2.2 代码

var constructMaximumBinaryTree = function(nums) {
    if(!nums.length) return null;
    let rootVal = Math.max(...nums);
    let cutIndex = nums.indexOf(rootVal);
    let root = new TreeNode(rootVal);

    root.left = constructMaximumBinaryTree(nums.slice(0 , cutIndex));
    root.right = constructMaximumBinaryTree(nums.slice(cutIndex + 1));

    return root;
};

3. leetcode108 将有序数组转换为二叉搜索树

3.1 思路

这题找根节点思路是直接取数组中点，因为数组是已经排好序的，别的都一样，看代码。

3.2 代码

var sortedArrayToBST = function(nums) {
    if(!nums.length) return null;
    let cutIndex = Math.floor((nums.length) / 2);
    let rootVal = nums[cutIndex];
    let root = new TreeNode(rootVal);
    
    root.left = sortedArrayToBST(nums.slice(0 , cutIndex));
    root.right = sortedArrayToBST(nums.slice(cutIndex + 1));

    return root;
};