0654.最大二叉树

654.最大二叉树

力扣题目地址

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下:

  • 二叉树的根是数组中的最大元素。
  • 左子树是通过数组中最大值左边部分构造出的最大二叉树。
  • 右子树是通过数组中最大值右边部分构造出的最大二叉树。

通过给定的数组构建最大二叉树,并且输出这个树的根节点。

示例 :

654.最大二叉树

提示:

给定的数组的大小在 [1, 1000] 之间。

《代码随想录》算法视频公开课又是构造二叉树,又有很多坑!| LeetCode:654.最大二叉树,相信结合视频在看本篇题解,更有助于大家对本题的理解

思路

最大二叉树的构建过程如下:

654.最大二叉树

构造树一般采用的是前序遍历,因为先构造中间节点,然后递归构造左子树和右子树。

  • 确定递归函数的参数和返回值

参数传入的是存放元素的数组,返回该数组构造的二叉树的头结点,返回类型是指向节点的指针。

代码如下:

TreeNode* constructMaximumBinaryTree(vector<int>& nums)

  • 确定终止条件

题目中说了输入的数组大小一定是大于等于1的,所以我们不用考虑小于1的情况,那么当递归遍历的时候,如果传入的数组大小为1,说明遍历到了叶子节点了。

那么应该定义一个新的节点,并把这个数组的数值赋给新的节点,然后返回这个节点。 这表示一个数组大小是1的时候,构造了一个新的节点,并返回。

代码如下:

TreeNode* node = new TreeNode(0);
if (nums.size() == 1) {
    node->val = nums[0];
    return node;
}
  • 确定单层递归的逻辑

这里有三步工作

  1. 先要找到数组中最大的值和对应的下标, 最大的值构造根节点,下标用来下一步分割数组。

代码如下:

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;
  1. 最大值所在的下标左区间 构造左子树

这里要判断maxValueIndex > 0,因为要保证左区间至少有一个数值。

代码如下:

if (maxValueIndex > 0) {
    vector<intnewVec(nums.begin(), nums.begin() + maxValueIndex);
    node->left = constructMaximumBinaryTree(newVec);
}
  1. 最大值所在的下标右区间 构造右子树

判断maxValueIndex < (nums.size() - 1),确保右区间至少有一个数值。

代码如下:

if (maxValueIndex < (nums.size() - 1)) {
    vector<intnewVec(nums.begin() + maxValueIndex + 1, nums.end());
    node->right = constructMaximumBinaryTree(newVec);
}

这样我们就分析完了,整体代码如下:(详细注释)

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(也就是数组),但逻辑比较清晰。

和文章二叉树:构造二叉树登场!中一样的优化思路,就是每次分隔不用定义新的数组,而是通过下标索引直接在原数组上操作。

优化后代码如下:

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判断,为了不让空节点进入递归)


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,就终止了。

总结

这道题目其实和 二叉树:构造二叉树登场! 是一个思路,比二叉树:构造二叉树登场! 还简单一些。

注意类似用数组构造二叉树的题目,每次分隔尽量不要定义新的数组,而是通过下标索引直接在原数组上操作,这样可以节约时间和空间上的开销。

一些同学也会疑惑,什么时候递归函数前面加if,什么时候不加if,这个问题我在最后也给出了解释。

其实就是不同代码风格的实现,一般情况来说:如果让空节点(空指针)进入递归,就不加if,如果不让空节点进入递归,就加if限制一下, 终止条件也会相应的调整。

其他语言版本

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

(版本一) 基础版

# 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
        

(版本二) 使用下标


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))

(版本三) 使用切片


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

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

/**
 * 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

新建数组法:

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;
};

使用数组索引法:

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

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

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

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

新建数组:

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,
        })))
    }
}

数组索引:

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#

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;

}