Tino又想吃肉了

将有序数组转为二叉搜索树

Note swift algorithm leetcode tree
Word count: 560Reading time: 2 min
2021/03/25

根据一个有序数组建立平衡二叉搜索树

给定一个有序的数组，如nums = [-10,-3,0,5,9]

高度平衡二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

二叉树定义如下

1
2
3
4
5
6
7
8
9
10
11
12
class TreeNode {
 public var val: Int
 public var left: TreeNode?
 public var right: TreeNode?
 public init() { self.val = 0; self.left = nil; self.right = nil; }
 public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
    self.val = val
    self.left = left
    self.right = right
 }
}

本题采用递归的实现方法。先说解题思路：由于数组已经是升序的了，那么我们第一个想法就是找到数组的中间元素，并以它的值作为根节点。那么接下来的节点怎么办呢？可以应用树的特性，每个二叉树节点本身也是一颗树，那么我们在第一次找到mid元素，下一次便用mid元素划分成两个数组，分别找到他们的中间元素作为最开始的root的left和right节点，并一直递归下去，就可以建成平衡二叉搜索树啦。

下面放实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    func sortedArrayToBST(_ nums: [Int]) -> TreeNode? {
        guard nums.count>0 else{
            return nil
        }

        return dfs(nums,0,nums.count-1)

    }
    func dfs(_ nums:[Int],_ lfs:Int,_ rfs:Int) -> TreeNode?{
        if lfs > rfs {
            return nil
        }
        let mid = lfs + (rfs - lfs)/2

        var root = TreeNode.init(nums[mid])

        root.left = dfs(nums,lfs,mid-1)

        root.right = dfs(nums,mid+1,rfs)

        return root
    }
}

代码很简单，需要注意的有要防止数组本身为空的情况，和在lfs>rfs时返回nil

如果将问题推广，到更一般的情况呢？比如给你的是一颗没有排序的普通二叉树。

这个时候只需要先进行一次二叉树遍历，记录所有节点的值并排序，最后按照上述方法递归实现即可。

树还是挺重要的，解题思路和方法也比较巧妙跟多样，需要多体会理解。
记录思路跟实现代码，及时回顾

Tino Wu

CATALOG
  1. 1. 给定一个有序的数组，如nums = [-10,-3,0,5,9]
    1. 1.1. 本题采用递归的实现方法。先说解题思路：由于数组已经是升序的了，那么我们第一个想法就是找到数组的中间元素，并以它的值作为根节点。那么接下来的节点怎么办呢？可以应用树的特性，每个二叉树节点本身也是一颗树，那么我们在第一次找到mid元素，下一次便用mid元素划分成两个数组，分别找到他们的中间元素作为最开始的root的left和right节点，并一直递归下去，就可以建成平衡二叉搜索树啦。
  2. 2. 如果将问题推广，到更一般的情况呢？比如给你的是一颗没有排序的普通二叉树。
    1. 2.1. 这个时候只需要先进行一次二叉树遍历，记录所有节点的值并排序，最后按照上述方法递归实现即可。
Total : 35
2022
2021
swift iOS Tools algorithm leetcode tree 动态规划 计网 DFS算法 双指针 排序 BFS 性能优化 底层原理 操作系统 启动流程
Note