网站建设找云尚网络,网站开发厂商,宣传部总结网站建设,晋江论坛晋江文学城网友留言区构造二叉树最好都是使用前序遍历#xff1b;中左右的顺序。
654. 最大二叉树
中等
636
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
创建一个根节点#xff0c;其值为 nums 中的最大值。递归地在最大值 左边 的 子数组前缀上 构建…构造二叉树最好都是使用前序遍历中左右的顺序。
654. 最大二叉树
中等
636
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
创建一个根节点其值为 nums 中的最大值。递归地在最大值 左边 的 子数组前缀上 构建左子树。递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums 构建的 最大二叉树 。 示例 1 输入nums [3,2,1,6,0,5]
输出[6,3,5,null,2,0,null,null,1]
解释递归调用如下所示
- [3,2,1,6,0,5] 中的最大值是 6 左边部分是 [3,2,1] 右边部分是 [0,5] 。- [3,2,1] 中的最大值是 3 左边部分是 [] 右边部分是 [2,1] 。- 空数组无子节点。- [2,1] 中的最大值是 2 左边部分是 [] 右边部分是 [1] 。- 空数组无子节点。- 只有一个元素所以子节点是一个值为 1 的节点。- [0,5] 中的最大值是 5 左边部分是 [0] 右边部分是 [] 。- 只有一个元素所以子节点是一个值为 0 的节点。- 空数组无子节点。示例 2 输入nums [3,2,1]
输出[3,null,2,null,1]
分析主要是先找到数组中最大值的和下标然后标记下来。再使用递归遍历的方法对左右的数组进行分割进行递归的遍历。递归终止的条件是数组只有一个元素时才终止。这时递归要结束。
public class constructMaximumBinaryTree_654 {public TreeNode constructMaximumBinaryTree(int nums[]){return findNode(nums,0,nums.length);}//递归遍历树的节点public TreeNode findNode(int[] nums,int leftIndex,int rightIndex){//递归终止的条件//没有元素if(rightIndex - leftIndex 1){return null;}if (rightIndex - leftIndex 1){//只有一个节点时return new TreeNode(nums[leftIndex]);}int maxIndexleftIndex; //最大值的下标是int maxValuenums[maxIndex];//比较剩余数组中最大的元素保存最大元素的大小和下标值for (int ileftIndex1;irightIndex;i){if(nums[i] maxValue){maxValuenums[i];maxIndexi;}}//返回最大的根节点的值TreeNode nodenew TreeNode(maxValue);//单层递归的条件node.leftfindNode(nums,leftIndex,maxIndex);//递归遍历左子树node.rightfindNode(nums,maxIndex1,rightIndex);//右子树return node;}
}
