二叉树二叉搜索树第K小的元素

0x00 题目

给定一个二叉搜索树的根节点 root
和一个整数 k
请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）

---

0x01 思路

方法一：
中序 遍历二叉搜索树
用一个 数组 存起来
当数组的 数量 等于 k 时
最后一个元素就是第 k 小的

方法二：
中序 遍历 二叉搜索树，是递增的
使用一个标记来记录 k
第递归一次，就把 k 减小 1
当 k 为 0 时，找到目标

---

0x02 解法

语言：Swift

树节点：TreeNode

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

解法：

    func kthSmallest(_ root: TreeNode?, _ k: Int) -> Int {
        var res = Int.min
        var i = k

        func dfs(_ root: TreeNode?) {
            guard let r = root else { return }

            if i == 0 {
                return
            }
            
			// 前序遍历位置
            dfs(r.left)

			// 中序遍历位置
            i -= 1
            if i == 0 {
                res = r.val
            }

            dfs(r.right)
            // 后序遍历位置
        }

        dfs(root)

        return res
    }

---

小五笔应用

---

这篇好文章是转载于：学新通技术网