2021/03/26 刷算法第一天 二叉树(1)

选择排序和归并排序，其实本质上就是二叉树的前序遍历和后序遍历的问题。

• 选择排序：

    void selectionSort(int[] arr, int left, int right) {
        if (left == right)
            return;
  
        int mid = sort(arr, left, right); // 将数组排序后，数组一分为二
        // 左子数组排序
        selectionSort(arr, left, mid);
        // 右子数组排序
        selectionSort(arr, mid + 1, right);
    }
  
    // sort函数就是排序细节，这里不再写出

• 归并排序

    void mergeSort(int[] arr, int left, int right) {
        if (left > right)
            return;
  
        mergeSort(arr, left, (left + right) / 2); // 左子数组排序
        mergeSort(arr, (left + right) / 2 + 1, right) // 右子数组排序
  
        sort(arr, left, right); // 排序总数组
    }
  
    // sort函数就是排序细节，这里不再写出

二叉树的问题，难点(解题点)就是找出：每一个子步骤应该做什么。找到解题点后，选择对应的前序、中序、后序遍历即可解决问题

今天解决了LeetCode几个二叉树问题：

1. 226.【翻转二叉树】：
2. 116.【填充二叉树节点的右侧指针】
3. 114.【将二叉树展开为链表】
4. 654.【最大二叉树】
5. 110.【平衡二叉树】
   解题思路：
   每个节点应该做的事：获取左树高度和右树高度，如果左右树高度差绝对值大于1，说明肯定不是平衡二叉树，返回-1，否则返回该节点高度；
   因此，判断条件不应该只是左右树高度差绝对值大于1，应该为(leftHeight == -1 || rightHeight == -1 || Math.abs)