//
// E_111_MinimumDepthOfBinaryTree.swift
// AlgorithmLeetCode
//
// Created by okerivy on 2017/3/10.
// Copyright ? 2017年 okerivy. All rights reserved.
// https://leetcode.com/problems/minimum-depth-of-binary-tree
import Foundation
// MARK: - 題目名稱: 111. Minimum Depth of Binary Tree
/* MARK: - 所屬類別:
標(biāo)簽: Tree, Depth-first Search, Breadth-first Search
相關(guān)題目:
(M) Binary Tree Level Order Traversal
(E) Maximum Depth of Binary Tree
*/
/* MARK: - 題目英文:
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
different from maximum depth. if a node only has one child, the depth will be 1 + child depth.
*/
/* MARK: - 題目翻譯:
給定一個(gè)二叉樹曙搬，找到它的最小深度置侍。
最小深度是沿著最短路徑從根節(jié)點(diǎn)到最近的葉節(jié)點(diǎn)的節(jié)點(diǎn)數(shù)量跨嘉。
*/
/* MARK: - 解題思路:
和之前的一題求二叉樹的最大深度的題目104. Maximum Depth of Binary Tree基本完全一致
區(qū)別在于需要求出根節(jié)點(diǎn)到最近的葉子節(jié)點(diǎn)的深度琅轧，我們?nèi)匀皇褂帽闅v的方式
不同于最大深度僻澎。如果一個(gè)節(jié)點(diǎn)只有一個(gè)，深度將是1 +子結(jié)點(diǎn)的深度该溯。
*/
// FIXME: 沒有完成
/* MARK: - 復(fù)雜度分析:
*/
// MARK: - 代碼:
private class Solution {
// 找到它的最小深度
func minDepth(_ root: TreeNode?) -> Int {
guard let root = root else {
return 0
}
if (root.left == nil) { return minDepth(root.right) + 1}
if (root.right == nil) { return minDepth(root.left) + 1}
return min(minDepth(root.left), minDepth(root.right)) + 1
}
}
// MARK: - 測試代碼:
// MARK: - 測試代碼:
func minimumDepthOfBinaryTree() {
let root1 = CreateBinaryTree().convertArrayToTree([4, 2, 6, 1, 3, 5, -1, 9])
let root2 = CreateBinaryTree().convertArrayToTree([3, Int.min, 20, 15, 7, 8, Int.min, Int.min, 9, 10])
let root3 = CreateBinaryTree().convertArrayToBSTree([8,2,10,9,11,1,7])
print(Solution().minDepth(root1), CreateBinaryTree().isValidBST(root: root1))
print(Solution().minDepth(root2), CreateBinaryTree().isValidBST(root: root2))
print(Solution().minDepth(root3), CreateBinaryTree().isValidBST(root: root3))
}
