选择排序和归并排序,其实本质上就是二叉树的前序遍历和后序遍历的问题。
选择排序:
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几个二叉树问题:
- 226.【翻转二叉树】:
- 116.【填充二叉树节点的右侧指针】
- 114.【将二叉树展开为链表】
- 654.【最大二叉树】
- 110.【平衡二叉树】
解题思路:
每个节点应该做的事:获取左树高度和右树高度,如果左右树高度差绝对值大于1,说明肯定不是平衡二叉树,返回-1,否则返回该节点高度;
因此,判断条件不应该只是左右树高度差绝对值大于1,应该为(leftHeight == -1 || rightHeight == -1 || Math.abs)