LeetCode——二叉树的总结问题-白红宇

LeetCode——二叉树的总结问题

阅读量：600 次

发布时间：2019-03-11

本文共 2827 字，大约阅读时间需要 9 分钟。

以下是针对上述问题的逐个解答：

1. 将有序数组转换为高度平衡二叉搜索树

方法： 中位点分割法确保左右子树高度差不超过1。具体步骤如下：

-selectors sortedArrayToBST(int[] array, int left, int right) {if (left > right) return null;int mid = left + (right - left) / 2;TreeNode root = new TreeNode(array[mid]);root.left = sortedArrayToBST(array, left, mid - 1);root.right = sortedArrayToBST(array, mid + 1, right);return root;}

说明： 中位点分割确保左右子树的高度差不会超过1。例如，对于数组[-10,-3,0,5,9]，中点为2（索引2），根为0，左子树[-10,-3]（高度1），右子树[5,9]（高度1），符合高度平衡条件。

2. 在二叉搜索树中找到众数

方法： 使用中序遍历获取升序数组，再用滑动窗口找最大出现频率。

-selectors test(int[] arr) {List

list = new ArrayList();dfs(root, list);List

sortedList = new ArrayList(list);int[] array = sortedList.stream().mapToInt(Integer::intValue).toArray();int count = 0, maxCount = 0, left = 0, right = 0;List

res = new ArrayList();while (left < array.length && right < array.length) {while (right < array.length && array[left] == array[right]) {count++;right++;}if (maxCount < count) {maxCount = count;if (!res.isEmpty()) res.remove(res.size() - 1);res.add(array[left]);} else if (maxCount == count) {maxCount = count;res.add(array[left]);}count = 0;left = right;}return res.toArray(new int[0]);}

说明： 中序遍历后数组为升序，滑动窗口从数组两端扩展，找出出现次数最多的元素作为众数。

3. 求二叉树的最小深度

方法： BFS层序遍历，同时记录每个节点的深度。

-selectors int depth(TreeNode node) {if (node == null) return 0;int leftDepth = depth(node.left);int rightDepth = depth(node.right);return Math.max(leftDepth, rightDepth) + 1;}

说明： 从根节点开始，层序遍历，每层记录深度，直到叶子节点，其中最小深度即最大深度。

4. 每层树的最大值

方法： BFS层序遍历，同时维护每层的最大值。

-selectors int[] maxOfEachLevel(TreeNode root) {List

currentLevel = new ArrayList();currentLevel.add(root.val);List

nextLevel = new ArrayList();List

result = new ArrayList();while (!currentLevel.isEmpty()) {int max = Integer.MIN_VALUE;for (Integer num : currentLevel) max = Math.max(max, num);result.add(max);for (Integer num : currentLevel) {if (num.left != null) nextLevel.add(num.left.val);if (num.right != null) nextLevel.add(num.right.val);}currentLevel = nextLevel;nextLevel.clear();}return result.toArray(new int[0]);}

说明： 每层遍历时，记录当前层的最大值并保存到结果中，逐层进行。

5. 二叉树中的路径和（最大）

方法： 用递归，从下往上选择保留最大的路径。

-selectors int calculateMaxPathSum(TreeNode root) {if (root == null) return Integer.MIN_VALUE;int leftSum = calculateMaxPathSum(root.left);int rightSum = calculateMaxPathSum(root.right);int maxSingle = Math.max(leftSum, rightSum);return root.val + Math.max(0, maxSingle);}

说明： 递归方式下，每个节点选取左右子树中的较大路径和，并加上自身值，如果子树的路径和为负，选择不加入。

6. 将二叉搜索树转换为双链表

方法： 中序遍历得到升序序列，反向链接前驱和后驱。

-selectors Node treeToDoublyList(Node root) {List

list = new ArrayList();dfs(root, list);Node head = list.get(0);if (head != null) head.left = null;for (int i = 1; i < list.size(); i++) {list.get(i).left = list.get(i - 1);list.get(i - 1).right = list.get(i);}return head;}

说明： 中序遍历存储节点序列，采用递归方式，构建双链表时反向连接前驱和后驱。

总结

通过以上详细步骤，可以实现对每个问题的有效解决方案，确保逻辑正确性和算法高效性。每个问题的核心在于特定数据结构和遍历方式的应用，确保算法复杂度和性能达到要求。

转载地址：http://bcltz.baihongyu.com/

你可能感兴趣的文章

OpenEuler23.03欧拉系统_安装瀚高数据库企业版6.0.4_openeuler切换root用户_su:拒绝权限_passwd: 鉴定令牌操作错误---国产瀚高数据库工作笔记001