算法第二十天|二叉树 -----二轮第一天|数组

669. 修剪二叉搜索树

/**
     * 函数定义   返回范围在[low,high]的二叉搜索树的新的根节点
     * @param root
     * @param low
     * @param high
     * @return
     */
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) {
            return root;
        }
        if (root.val < low) {
            root.left = null;
            return trimBST(root.right, low, high);
        } else if (root.val == low){
            root.left = null;
            root.right = trimBST(root.right, low, high);
            return root;
        } else if (root.val > low && root.val < high) {
            root.left = trimBST(root.left, low, high);
            root.right = trimBST(root.right, low, high);
            return root;
        } else if (root.val == high) {
            root.right = null;
            root.left = trimBST(root.left, low, high);
            return root;
        } else {
            return trimBST(root.left, low, high);
        }
    }

该题将所有举例列出来即可，画一个二叉树，把五种可能挨着写出来，题目就解出来了

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

     public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) {
            return null;
        }
        return splitTreeNode(nums, 0, nums.length -1);
      }

    private TreeNode splitTreeNode(int[] nums, int leftIndex, int rightIndex) {
        if (leftIndex > rightIndex || leftIndex < 0 || rightIndex > nums.length -1) {
            return null;
        }
        if (leftIndex == rightIndex) {
            return new TreeNode(nums[leftIndex]);
        }

        int midIndex = leftIndex + (rightIndex - leftIndex) / 2;

        TreeNode root = new TreeNode(nums[midIndex]);
        root.left = splitTreeNode(nums, leftIndex, midIndex -1);
        root.right = splitTreeNode(nums, midIndex + 1, rightIndex);
        return root;
    }

538.把二叉搜索树转换为累加树

   List<Integer> list = new ArrayList<>();

    public TreeNode convertBST(TreeNode root) {
        // 先进行中序遍历，将数据放入map中
        getPreOrder(root);
        Map<Integer, Integer> map = new TreeMap<>();
        for (int i = list.size()- 1; i >= 0 ; i--) {
            Integer value = list.get(i);
            if (i < list.size()- 1) {
                map.put(value, map.get(list.get(i + 1)) + value);
            } else  {
                map.put(value, value);
            }
        }
        doAddTreeNode(root, map);
        return root;
    }

    private void doAddTreeNode(TreeNode root, Map<Integer, Integer> map) {
        if (root == null) {
            return;
        }
        root.val = map.get(root.val);
        doAddTreeNode(root.left, map);
        doAddTreeNode(root.right, map);
    }

    private void getPreOrder(TreeNode root) {
        if (root == null) {
            return;
        }

        getPreOrder(root.left);
        list.add(root.val);
        getPreOrder(root.right);
    }


int sum;

public TreeNode convertBST2(TreeNode root) {
    sum = 0;
    getConvertBST(root);
    return root;
}

private void getConvertBST(TreeNode root) {
    if (root == null) {
        return;
    }

    getConvertBST(root.right);
    sum += root.val;
    root.val = sum;

    getConvertBST(root.left);
}

思路：先进行中序遍历，然后将数据存放在map中，进行累加，最后再存放回二叉树中

第二种方法，进行右中左的反中序遍历, 成功实现对整个数据的累加。

同步进行二轮的复习

算法题为啥还有二轮？死记硬背？并不是。

题目做对了一次，第二次不一定能够成功作对。算法题，大多是对方法的灵活运用，多做，勤练即可，习惯思维的碰撞。

从二轮开始，首先编写自己的解答方式，然后尝试对其进行优化改进

二轮|数组|二分查找

  public int search(int[] nums, int target) {
        int beginIndex = 0;
        int endIndex = nums.length - 1;
        while (beginIndex <= endIndex) {
            int midIndex = beginIndex + (endIndex - beginIndex) /2;
            if (nums[midIndex] < target) {
                beginIndex = midIndex + 1;
            } else if (nums[midIndex] > target) {
                endIndex = midIndex - 1;
            } else {
                return midIndex;
            }
        }
        return -1;
    }
    
    //-------------------------------------------方式二------------------------------------------------------

    public int search2(int[] nums, int target) {
        return searchByMid(nums, target, 0, nums.length - 1);
    }

    private int searchByMid(int[] nums, int target, int leftIndex, int rightIndex) {
        if (leftIndex < 0 || leftIndex > rightIndex || rightIndex > nums.length) {
            return -1;
        }
        int midIndex = leftIndex + (rightIndex - leftIndex) / 2;
        if (nums[midIndex] == target) {
            return midIndex;
        } else if (nums[midIndex] > target) {
            return searchByMid(nums, target, leftIndex, midIndex - 1);
        } else{
            return searchByMid(nums, target, midIndex + 1, rightIndex);
        }
    }

方式一使用迭代，不断更改beginIndex和endIndex的值；方式二使用递归

两种方式没啥太大的差异，使用迭代进行优化和总结。

二分查找是一个不断缩小取值范围，最终找到目标值的一个查找算法。

优化：

1. 在算法之初，可以将一些不合理的数据进行排除掉，减小数据的查询量，在我们实际工作中也是很有用的, 我将其称为check部分,之后的总结和优化使用该字表示。

• nums在题目中给出，个数在[1, 10000]之间。那么nums不用检查为空
• nums是一个升序数组，那么nums[0]最小，nums[nums.length - 1]最大。如果数组中最小值都比target大，或者最大值都比target小,那么数组中肯定不存在这个值

  public int search(int[] nums, int target) {
    if (nums[0] > target || nums[nums.length - 1] < target) {
        return -1;
    }
  }

2. 灵活使用左移运算符和右移运算符

int midIndex = beginIndex + (endIndex - beginIndex) /2;

右移定义：将一个数的各二进制位全部右移若干位，高位补0或补符号位，右边丢弃。

代码有除二的操作，众所周知，右移运算代替除二的操作，能够效率更高，所以可以改写为

int midIndex = beginIndex + (endIndex - beginIndex) >> 1;

但这里有个小问题，java难道没有做底层优化嘛？感觉java设计者们应该早就考虑过这些问题了。

我去搜索了一下资料, 感兴趣的小伙伴可以查看这篇文章：

灵魂拷问：用移位来代替除法运算真的效率高吗？Java 编译器到底有没有做除法优化？_c 除法 优化为 位移-CSDN博客

[!TIP]

在实际开发中，大可不必去要求位运算符，可读性着实不好。
但在写算法的过程中，我们面向的本身就是底层，java等语言或许提供了对应的能力，但是我们要写的就是这些能力。
比如：反转数组，Collections.reverse(arrayList);直接就实现了，但实际上要求我们实现的就是提供这个能力的方法

References:

灵魂拷问：用移位来代替除法运算真的效率高吗？Java 编译器到底有没有做除法优化？_c 除法 优化为 位移-CSDN博客