600 lines
18 KiB
Markdown
Executable File
600 lines
18 KiB
Markdown
Executable File
* [做项目（多个C++、Java、Go、测开、前端项目）](https://www.programmercarl.com/other/kstar.html)
|
||
* [刷算法（两个月高强度学算法）](https://www.programmercarl.com/xunlian/xunlianying.html)
|
||
* [背八股（40天挑战高频面试题）](https://www.programmercarl.com/xunlian/bagu.html)
|
||
|
||
|
||
# 654.最大二叉树
|
||
|
||
[力扣题目地址](https://leetcode.cn/problems/maximum-binary-tree/)
|
||
|
||
给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：
|
||
|
||
* 二叉树的根是数组中的最大元素。
|
||
* 左子树是通过数组中最大值左边部分构造出的最大二叉树。
|
||
* 右子树是通过数组中最大值右边部分构造出的最大二叉树。
|
||
|
||
通过给定的数组构建最大二叉树，并且输出这个树的根节点。
|
||
|
||
示例 ：
|
||
|
||
|
||
|
||
提示：
|
||
|
||
给定的数组的大小在 [1, 1000] 之间。
|
||
|
||
## 算法公开课
|
||
|
||
**[《代码随想录》算法视频公开课](https://programmercarl.com/other/gongkaike.html)：[又是构造二叉树，又有很多坑！| LeetCode：654.最大二叉树](https://www.bilibili.com/video/BV1MG411G7ox)，相信结合视频在看本篇题解，更有助于大家对本题的理解**。
|
||
|
||
|
||
## 思路
|
||
|
||
最大二叉树的构建过程如下：
|
||
|
||
|
||
|
||
构造树一般采用的是前序遍历，因为先构造中间节点，然后递归构造左子树和右子树。
|
||
|
||
* 确定递归函数的参数和返回值
|
||
|
||
参数传入的是存放元素的数组，返回该数组构造的二叉树的头结点，返回类型是指向节点的指针。
|
||
|
||
代码如下：
|
||
|
||
```CPP
|
||
TreeNode* constructMaximumBinaryTree(vector<int>& nums)
|
||
|
||
```
|
||
* 确定终止条件
|
||
|
||
题目中说了输入的数组大小一定是大于等于1的，所以我们不用考虑小于1的情况，那么当递归遍历的时候，如果传入的数组大小为1，说明遍历到了叶子节点了。
|
||
|
||
那么应该定义一个新的节点，并把这个数组的数值赋给新的节点，然后返回这个节点。 这表示一个数组大小是1的时候，构造了一个新的节点，并返回。
|
||
|
||
代码如下：
|
||
|
||
```CPP
|
||
TreeNode* node = new TreeNode(0);
|
||
if (nums.size() == 1) {
|
||
node->val = nums[0];
|
||
return node;
|
||
}
|
||
```
|
||
|
||
* 确定单层递归的逻辑
|
||
|
||
这里有三步工作
|
||
|
||
1. 先要找到数组中最大的值和对应的下标， 最大的值构造根节点，下标用来下一步分割数组。
|
||
|
||
代码如下：
|
||
```CPP
|
||
int maxValue = 0;
|
||
int maxValueIndex = 0;
|
||
for (int i = 0; i < nums.size(); i++) {
|
||
if (nums[i] > maxValue) {
|
||
maxValue = nums[i];
|
||
maxValueIndex = i;
|
||
}
|
||
}
|
||
TreeNode* node = new TreeNode(0);
|
||
node->val = maxValue;
|
||
```
|
||
|
||
2. 最大值所在的下标左区间 构造左子树
|
||
|
||
这里要判断maxValueIndex > 0，因为要保证左区间至少有一个数值。
|
||
|
||
代码如下：
|
||
```CPP
|
||
if (maxValueIndex > 0) {
|
||
vector<int> newVec(nums.begin(), nums.begin() + maxValueIndex);
|
||
node->left = constructMaximumBinaryTree(newVec);
|
||
}
|
||
```
|
||
|
||
3. 最大值所在的下标右区间 构造右子树
|
||
|
||
判断maxValueIndex < (nums.size() - 1)，确保右区间至少有一个数值。
|
||
|
||
代码如下：
|
||
|
||
```CPP
|
||
if (maxValueIndex < (nums.size() - 1)) {
|
||
vector<int> newVec(nums.begin() + maxValueIndex + 1, nums.end());
|
||
node->right = constructMaximumBinaryTree(newVec);
|
||
}
|
||
```
|
||
这样我们就分析完了，整体代码如下：（详细注释）
|
||
|
||
```CPP
|
||
class Solution {
|
||
public:
|
||
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
|
||
TreeNode* node = new TreeNode(0);
|
||
if (nums.size() == 1) {
|
||
node->val = nums[0];
|
||
return node;
|
||
}
|
||
// 找到数组中最大的值和对应的下标
|
||
int maxValue = 0;
|
||
int maxValueIndex = 0;
|
||
for (int i = 0; i < nums.size(); i++) {
|
||
if (nums[i] > maxValue) {
|
||
maxValue = nums[i];
|
||
maxValueIndex = i;
|
||
}
|
||
}
|
||
node->val = maxValue;
|
||
// 最大值所在的下标左区间 构造左子树
|
||
if (maxValueIndex > 0) {
|
||
vector<int> newVec(nums.begin(), nums.begin() + maxValueIndex);
|
||
node->left = constructMaximumBinaryTree(newVec);
|
||
}
|
||
// 最大值所在的下标右区间 构造右子树
|
||
if (maxValueIndex < (nums.size() - 1)) {
|
||
vector<int> newVec(nums.begin() + maxValueIndex + 1, nums.end());
|
||
node->right = constructMaximumBinaryTree(newVec);
|
||
}
|
||
return node;
|
||
}
|
||
};
|
||
```
|
||
|
||
以上代码比较冗余，效率也不高，每次还要切割的时候每次都要定义新的vector（也就是数组），但逻辑比较清晰。
|
||
|
||
和文章[二叉树：构造二叉树登场！](https://programmercarl.com/0106.从中序与后序遍历序列构造二叉树.html)中一样的优化思路，就是每次分隔不用定义新的数组，而是通过下标索引直接在原数组上操作。
|
||
|
||
优化后代码如下：
|
||
|
||
```CPP
|
||
class Solution {
|
||
private:
|
||
// 在左闭右开区间[left, right)，构造二叉树
|
||
TreeNode* traversal(vector<int>& nums, int left, int right) {
|
||
if (left >= right) return nullptr;
|
||
|
||
// 分割点下标：maxValueIndex
|
||
int maxValueIndex = left;
|
||
for (int i = left + 1; i < right; ++i) {
|
||
if (nums[i] > nums[maxValueIndex]) maxValueIndex = i;
|
||
}
|
||
|
||
TreeNode* root = new TreeNode(nums[maxValueIndex]);
|
||
|
||
// 左闭右开：[left, maxValueIndex)
|
||
root->left = traversal(nums, left, maxValueIndex);
|
||
|
||
// 左闭右开：[maxValueIndex + 1, right)
|
||
root->right = traversal(nums, maxValueIndex + 1, right);
|
||
|
||
return root;
|
||
}
|
||
public:
|
||
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
|
||
return traversal(nums, 0, nums.size());
|
||
}
|
||
};
|
||
```
|
||
|
||
## 拓展
|
||
|
||
可以发现上面的代码看上去简洁一些，**主要是因为第二版其实是允许空节点进入递归，所以不用在递归的时候加判断节点是否为空**
|
||
|
||
第一版递归过程：（加了if判断，为了不让空节点进入递归）
|
||
```CPP
|
||
|
||
if (maxValueIndex > 0) { // 这里加了判断是为了不让空节点进入递归
|
||
vector<int> newVec(nums.begin(), nums.begin() + maxValueIndex);
|
||
node->left = constructMaximumBinaryTree(newVec);
|
||
}
|
||
|
||
if (maxValueIndex < (nums.size() - 1)) { // 这里加了判断是为了不让空节点进入递归
|
||
vector<int> newVec(nums.begin() + maxValueIndex + 1, nums.end());
|
||
node->right = constructMaximumBinaryTree(newVec);
|
||
}
|
||
```
|
||
|
||
第二版递归过程： （如下代码就没有加if判断）
|
||
|
||
```
|
||
root->left = traversal(nums, left, maxValueIndex);
|
||
|
||
root->right = traversal(nums, maxValueIndex + 1, right);
|
||
```
|
||
|
||
第二版代码是允许空节点进入递归，所以没有加if判断，当然终止条件也要有相应的改变。
|
||
|
||
第一版终止条件，是遇到叶子节点就终止，因为空节点不会进入递归。
|
||
|
||
第二版相应的终止条件，是遇到空节点，也就是数组区间为0，就终止了。
|
||
|
||
## 总结
|
||
|
||
|
||
这道题目其实和 [二叉树：构造二叉树登场！](https://programmercarl.com/0106.从中序与后序遍历序列构造二叉树.html) 是一个思路，比[二叉树：构造二叉树登场！](https://programmercarl.com/0106.从中序与后序遍历序列构造二叉树.html) 还简单一些。
|
||
|
||
**注意类似用数组构造二叉树的题目，每次分隔尽量不要定义新的数组，而是通过下标索引直接在原数组上操作，这样可以节约时间和空间上的开销。**
|
||
|
||
一些同学也会疑惑，什么时候递归函数前面加if，什么时候不加if，这个问题我在最后也给出了解释。
|
||
|
||
其实就是不同代码风格的实现，**一般情况来说：如果让空节点（空指针）进入递归，就不加if，如果不让空节点进入递归，就加if限制一下， 终止条件也会相应的调整。**
|
||
|
||
## 其他语言版本
|
||
|
||
|
||
### Java
|
||
|
||
```Java
|
||
class Solution {
|
||
public TreeNode constructMaximumBinaryTree(int[] nums) {
|
||
return constructMaximumBinaryTree1(nums, 0, nums.length);
|
||
}
|
||
|
||
public TreeNode constructMaximumBinaryTree1(int[] nums, int leftIndex, int rightIndex) {
|
||
if (rightIndex - leftIndex < 1) {// 没有元素了
|
||
return null;
|
||
}
|
||
if (rightIndex - leftIndex == 1) {// 只有一个元素
|
||
return new TreeNode(nums[leftIndex]);
|
||
}
|
||
int maxIndex = leftIndex;// 最大值所在位置
|
||
int maxVal = nums[maxIndex];// 最大值
|
||
for (int i = leftIndex + 1; i < rightIndex; i++) {
|
||
if (nums[i] > maxVal){
|
||
maxVal = nums[i];
|
||
maxIndex = i;
|
||
}
|
||
}
|
||
TreeNode root = new TreeNode(maxVal);
|
||
// 根据maxIndex划分左右子树
|
||
root.left = constructMaximumBinaryTree1(nums, leftIndex, maxIndex);
|
||
root.right = constructMaximumBinaryTree1(nums, maxIndex + 1, rightIndex);
|
||
return root;
|
||
}
|
||
}
|
||
```
|
||
|
||
### Python
|
||
(版本一) 基础版
|
||
```python
|
||
# Definition for a binary tree node.
|
||
# class TreeNode:
|
||
# def __init__(self, val=0, left=None, right=None):
|
||
# self.val = val
|
||
# self.left = left
|
||
# self.right = right
|
||
class Solution:
|
||
def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
|
||
if len(nums) == 1:
|
||
return TreeNode(nums[0])
|
||
node = TreeNode(0)
|
||
# 找到数组中最大的值和对应的下标
|
||
maxValue = 0
|
||
maxValueIndex = 0
|
||
for i in range(len(nums)):
|
||
if nums[i] > maxValue:
|
||
maxValue = nums[i]
|
||
maxValueIndex = i
|
||
node.val = maxValue
|
||
# 最大值所在的下标左区间 构造左子树
|
||
if maxValueIndex > 0:
|
||
new_list = nums[:maxValueIndex]
|
||
node.left = self.constructMaximumBinaryTree(new_list)
|
||
# 最大值所在的下标右区间 构造右子树
|
||
if maxValueIndex < len(nums) - 1:
|
||
new_list = nums[maxValueIndex+1:]
|
||
node.right = self.constructMaximumBinaryTree(new_list)
|
||
return node
|
||
|
||
```
|
||
(版本二) 使用下标
|
||
```python
|
||
|
||
class Solution:
|
||
def traversal(self, nums: List[int], left: int, right: int) -> TreeNode:
|
||
if left >= right:
|
||
return None
|
||
maxValueIndex = left
|
||
for i in range(left + 1, right):
|
||
if nums[i] > nums[maxValueIndex]:
|
||
maxValueIndex = i
|
||
root = TreeNode(nums[maxValueIndex])
|
||
root.left = self.traversal(nums, left, maxValueIndex)
|
||
root.right = self.traversal(nums, maxValueIndex + 1, right)
|
||
return root
|
||
|
||
def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
|
||
return self.traversal(nums, 0, len(nums))
|
||
|
||
```
|
||
|
||
(版本三) 使用切片
|
||
|
||
```python
|
||
|
||
class Solution:
|
||
def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
|
||
if not nums:
|
||
return None
|
||
max_val = max(nums)
|
||
max_index = nums.index(max_val)
|
||
node = TreeNode(max_val)
|
||
node.left = self.constructMaximumBinaryTree(nums[:max_index])
|
||
node.right = self.constructMaximumBinaryTree(nums[max_index+1:])
|
||
return node
|
||
|
||
```
|
||
### Go
|
||
|
||
|
||
```go
|
||
func constructMaximumBinaryTree(nums []int) *TreeNode {
|
||
if len(nums) == 0 {
|
||
return nil
|
||
}
|
||
// 找到最大值
|
||
index := findMax(nums)
|
||
// 构造二叉树
|
||
root := &TreeNode {
|
||
Val: nums[index],
|
||
Left: constructMaximumBinaryTree(nums[:index]), //左半边
|
||
Right: constructMaximumBinaryTree(nums[index+1:]),//右半边
|
||
}
|
||
return root
|
||
}
|
||
func findMax(nums []int) (index int) {
|
||
for i, v := range nums {
|
||
if nums[index] < v {
|
||
index = i
|
||
}
|
||
}
|
||
return
|
||
}
|
||
```
|
||
|
||
### JavaScript
|
||
|
||
```javascript
|
||
/**
|
||
* Definition for a binary tree node.
|
||
* function TreeNode(val, left, right) {
|
||
* this.val = (val===undefined ? 0 : val)
|
||
* this.left = (left===undefined ? null : left)
|
||
* this.right = (right===undefined ? null : right)
|
||
* }
|
||
*/
|
||
/**
|
||
* @param {number[]} nums
|
||
* @return {TreeNode}
|
||
*/
|
||
var constructMaximumBinaryTree = function (nums) {
|
||
const BuildTree = (arr, left, right) => {
|
||
if (left > right)
|
||
return null;
|
||
let maxValue = -1;
|
||
let maxIndex = -1;
|
||
for (let i = left; i <= right; ++i) {
|
||
if (arr[i] > maxValue) {
|
||
maxValue = arr[i];
|
||
maxIndex = i;
|
||
}
|
||
}
|
||
let root = new TreeNode(maxValue);
|
||
root.left = BuildTree(arr, left, maxIndex - 1);
|
||
root.right = BuildTree(arr, maxIndex + 1, right);
|
||
return root;
|
||
}
|
||
let root = BuildTree(nums, 0, nums.length - 1);
|
||
return root;
|
||
};
|
||
```
|
||
|
||
### TypeScript
|
||
|
||
> 新建数组法：
|
||
|
||
```typescript
|
||
function constructMaximumBinaryTree(nums: number[]): TreeNode | null {
|
||
if (nums.length === 0) return null;
|
||
let maxIndex: number = 0;
|
||
let maxVal: number = nums[0];
|
||
for (let i = 1, length = nums.length; i < length; i++) {
|
||
if (nums[i] > maxVal) {
|
||
maxIndex = i;
|
||
maxVal = nums[i];
|
||
}
|
||
}
|
||
const rootNode: TreeNode = new TreeNode(maxVal);
|
||
rootNode.left = constructMaximumBinaryTree(nums.slice(0, maxIndex));
|
||
rootNode.right = constructMaximumBinaryTree(nums.slice(maxIndex + 1));
|
||
return rootNode;
|
||
};
|
||
```
|
||
|
||
> 使用数组索引法：
|
||
|
||
```typescript
|
||
function constructMaximumBinaryTree(nums: number[]): TreeNode | null {
|
||
// 左闭右开区间[begin, end)
|
||
function recur(nums: number[], begin: number, end: number): TreeNode | null {
|
||
if (begin === end) return null;
|
||
let maxIndex: number = begin;
|
||
let maxVal: number = nums[begin];
|
||
for (let i = begin + 1; i < end; i++) {
|
||
if (nums[i] > maxVal) {
|
||
maxIndex = i;
|
||
maxVal = nums[i];
|
||
}
|
||
}
|
||
const rootNode: TreeNode = new TreeNode(maxVal);
|
||
rootNode.left = recur(nums, begin, maxIndex);
|
||
rootNode.right = recur(nums, maxIndex + 1, end);
|
||
return rootNode;
|
||
}
|
||
return recur(nums, 0, nums.length);
|
||
};
|
||
```
|
||
|
||
|
||
|
||
### C
|
||
|
||
```c
|
||
struct TreeNode* traversal(int* nums, int left, int right) {
|
||
//若左边界大于右边界，返回NULL
|
||
if(left >= right)
|
||
return NULL;
|
||
|
||
//找出数组中最大数坐标
|
||
int maxIndex = left;
|
||
int i;
|
||
for(i = left + 1; i < right; i++) {
|
||
if(nums[i] > nums[maxIndex])
|
||
maxIndex = i;
|
||
}
|
||
|
||
//开辟结点
|
||
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
|
||
//将结点的值设为最大数组数组元素
|
||
node->val = nums[maxIndex];
|
||
//递归定义左孩子结点和右孩子结点
|
||
node->left = traversal(nums, left, maxIndex);
|
||
node->right = traversal(nums, maxIndex + 1, right);
|
||
return node;
|
||
}
|
||
|
||
struct TreeNode* constructMaximumBinaryTree(int* nums, int numsSize){
|
||
return traversal(nums, 0, numsSize);
|
||
}
|
||
```
|
||
|
||
### Swift
|
||
```swift
|
||
func constructMaximumBinaryTree(_ nums: inout [Int]) -> TreeNode? {
|
||
return traversal(&nums, 0, nums.count)
|
||
}
|
||
|
||
func traversal(_ nums: inout [Int], _ left: Int, _ right: Int) -> TreeNode? {
|
||
if left >= right {
|
||
return nil
|
||
}
|
||
|
||
var maxValueIndex = left
|
||
for i in (left + 1)..<right {
|
||
if nums[i] > nums[maxValueIndex] {
|
||
maxValueIndex = i
|
||
}
|
||
}
|
||
|
||
let root = TreeNode(nums[maxValueIndex])
|
||
|
||
root.left = traversal(&nums, left, maxValueIndex)
|
||
root.right = traversal(&nums, maxValueIndex + 1, right)
|
||
return root
|
||
}
|
||
```
|
||
|
||
### Scala
|
||
|
||
```scala
|
||
object Solution {
|
||
def constructMaximumBinaryTree(nums: Array[Int]): TreeNode = {
|
||
if (nums.size == 0) return null
|
||
// 找到数组最大值
|
||
var maxIndex = 0
|
||
var maxValue = Int.MinValue
|
||
for (i <- nums.indices) {
|
||
if (nums(i) > maxValue) {
|
||
maxIndex = i
|
||
maxValue = nums(i)
|
||
}
|
||
}
|
||
|
||
// 构建一棵树
|
||
var root = new TreeNode(maxValue, null, null)
|
||
|
||
// 递归寻找左右子树
|
||
root.left = constructMaximumBinaryTree(nums.slice(0, maxIndex))
|
||
root.right = constructMaximumBinaryTree(nums.slice(maxIndex + 1, nums.length))
|
||
|
||
root // 返回root
|
||
}
|
||
}
|
||
```
|
||
|
||
### Rust
|
||
|
||
新建数组：
|
||
|
||
```rust
|
||
use std::cell::RefCell;
|
||
use std::rc::Rc;
|
||
impl Solution{
|
||
pub fn construct_maximum_binary_tree(mut nums: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
|
||
if nums.is_empty() {
|
||
return None;
|
||
}
|
||
let mut max_value_index = 0;
|
||
for i in 0..nums.len() {
|
||
if nums[max_value_index] < nums[i] {
|
||
max_value_index = i;
|
||
}
|
||
}
|
||
let right = Self::construct_maximum_binary_tree(nums.split_off(max_value_index + 1));
|
||
let root = nums.pop().unwrap();
|
||
let left = Self::construct_maximum_binary_tree(nums);
|
||
Some(Rc::new(RefCell::new(TreeNode {
|
||
val: root,
|
||
left,
|
||
right,
|
||
})))
|
||
}
|
||
}
|
||
```
|
||
|
||
数组索引：
|
||
```rust
|
||
use std::cell::RefCell;
|
||
use std::rc::Rc;
|
||
impl Solution {
|
||
pub fn construct_maximum_binary_tree(nums: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
|
||
Self::traversal(&nums, 0, nums.len())
|
||
}
|
||
|
||
pub fn traversal(nums: &Vec<i32>, left: usize, right: usize) -> Option<Rc<RefCell<TreeNode>>> {
|
||
if left >= right {
|
||
return None;
|
||
}
|
||
let mut max_value_index = left;
|
||
for i in left + 1..right {
|
||
if nums[max_value_index] < nums[i] {
|
||
max_value_index = i;
|
||
}
|
||
}
|
||
let mut root = TreeNode::new(nums[max_value_index]);
|
||
root.left = Self::traversal(nums, left, max_value_index);
|
||
root.right = Self::traversal(nums, max_value_index + 1, right);
|
||
Some(Rc::new(RefCell::new(root)))
|
||
}
|
||
}
|
||
```
|
||
### C#
|
||
```csharp
|
||
public TreeNode ConstructMaximumBinaryTree(int[] nums)
|
||
{
|
||
if (nums.Length == 0) return null;
|
||
int rootValue = nums.Max();
|
||
TreeNode root = new TreeNode(rootValue);
|
||
int rootIndex = Array.IndexOf(nums, rootValue);
|
||
|
||
root.left = ConstructMaximumBinaryTree(nums.Take(rootIndex).ToArray());
|
||
root.right = ConstructMaximumBinaryTree(nums.Skip(rootIndex + 1).ToArray());
|
||
return root;
|
||
|
||
}
|
||
```
|
||
|
||
|