LetCode in Swift (654-Maximum Binary Tree)

文章目录

1. 1. 文档更新说明
2. 2. 前言
3. 3. 771. Jewels and Stones
   1. 3.1. Example1
   2. 3.2. Note
   3. 3.3. Solution

文档更新说明

• 最后更新 2018年03月08日
• 首次更新 2018年03月08日

前言

　　使用Swift语言完成LetCode题目,中等难度题目.涉及到二叉树,是一道好题目.

771. Jewels and Stones

Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

1. The root is the maximum number in the array.
2. The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
3. The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.

Construct the maximum tree by the given array and output the root node of this tree.

Example1

Input: [3,2,1,6,0,5]
Output: return the tree root node representing the following tree:

      6
    /   \
   3     5
    \    / 
     2  0   
       \
        1   

Note

The size of the given array will be in the range [1,1000].

Solution

　　这是一道二叉树题目,根据题意,很容易联想”大事化小”的方法,下面采用递归算法解决问题.
　　先是找到最大的数字,创建节点.之后最大数字的左右两边又是两个数组,这两个数字又继续看成一个独立的数组,采用同样的方法,查找最大值,创立节点.这就是”大事化小”的思想了.
　　当然本题如果不采用递归算法,就需要采用栈的方式来解决,难度大一些,后期我再补充上非递归方法.

//Definition for a binary tree node.
public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    
    public init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}

//递归算法
class Solution {
    func constructMaximumBinaryTree(_ nums: [Int]) -> TreeNode? {
        //这里需要条件来判断递归终止
        if nums.count == 0 {
            return nil
        }
        let maxNums = nums.max()
        let index = nums.index(of: maxNums!)
        let rootNode = TreeNode(maxNums!)
        rootNode.left = constructMaximumBinaryTree(Array(nums[0..<index!]))
        rootNode.right = constructMaximumBinaryTree(Array(nums[index!+1 ..< nums.count]))
        return rootNode
    }
}

let s = Solution()
let node = s.constructMaximumBinaryTree([3,2,1,6,0,5])

//非递归算法 (后期更新)