代码随想录算法训练营之JAVA｜第十七天| 654. 最大二叉树

今天是第17天刷leetcode，立个flag，打卡60天。

算法挑战链接

654. 最大二叉树https://leetcode.cn/problems/maximum-binary-tree/description/

第一想法

错误的想法，就不说了。

看完代码随想录之后的想法 

用递归模拟真实的过程

如果我们我们自己使用手动来画我们会怎么画？

我想大概的一个流程应该是这样的

1. 找到最大值，形成节点
2. 在最大值的左边，重复
3. 在最大值的右边，重复
4. 值到所有的数组中的数都形成数的节点

于是代码也就是对这个流程的描述了

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {return repeatByNums(nums, 0, nums.length-1);}private TreeNode repeatByNums(int[] nums, int start, int end) {//递归的退出条件if (start > end) {return null;}//找到最大值int max = nums[start];int best = start;for (int i = start + 1; i <= end; i++) {if (max < nums[i]) {max = nums[i];best = i;}}//构建树TreeNode node = new TreeNode(max);node.left = repeatByNums(nums, start, best - 1);node.right = repeatByNums(nums, best + 1, end);return node;}
}

实现过程中遇到哪些困难 

在写找最大值的时候，写成了 i < end, 应该是 i <= end。

为什么呢，因为nums[end]也是需要被比较的。

今日收获

让我重新看待了递归这个方法，递归可以解决我们重复的动作可以解决的题目。