// 二分木ノードの定義
public class BinaryNode {
    public var value: Int
    public var leftChild: BinaryNode?
    public var rightChild: BinaryNode?
    
    public init(value: Int) {
        self.value = value
    }
}

// 深さ優先探索（前順）
func preorder(node: BinaryNode?) -> [Int] {
    guard let currentNode = node else { return [] }
    return [currentNode.value] + preorder(node: currentNode.leftChild) + preorder(node: currentNode.rightChild)
}

概念

前順探索では、まず根ノードを訪問し、その後左部分木、右部分木を順に探索します。

// 深さ優先探索（中順）
func inorder(node: BinaryNode?) -> [Int] {
    guard let currentNode = node else { return [] }
    return inorder(node: currentNode.leftChild) + [currentNode.value] + inorder(node: currentNode.rightChild)
}

中順探索では、まず左部分木を探索し、次に根ノード、最後に右部分木を探索します。

// 深さ優先探索（後順）
func postorder(node: BinaryNode?) -> [Int] {
    guard let currentNode = node else { return [] }
    return postorder(node: currentNode.leftChild) + postorder(node: currentNode.rightChild) + [currentNode.value]
}

後順探索では、左部分木、右部分木を探索した後に根ノードを訪問します。

// 幅優先探索
func levelOrder(root: BinaryNode?) -> [[Int]] {
    guard let rootNode = root else { return [] }
    var result: [[Int]] = []
    var queue: [BinaryNode] = [rootNode]
    
    while !queue.isEmpty {
        var currentLevelValues: [Int] = []
        for _ in 0..<queue.count {
            let currentNode = queue.removeFirst()
            currentLevelValues.append(currentNode.value)
            if let leftChild = currentNode.leftChild { queue.append(leftChild) }
            if let rightChild = currentNode.rightChild { queue.append(rightChild) }
        }
        result.append(currentLevelValues)
    }
    return result
}

幅優先探索は、各レベルごとにノードを訪問する方法です。キューを使用して、親ノードから子ノードへと順に処理を行います。

// 最大深さの計算（再帰版）
func maxDepth(_ node: BinaryNode?) -> Int {
    guard let currentNode = node else { return 0 }
    return max(maxDepth(currentNode.leftChild), maxDepth(currentNode.rightChild)) + 1
}

最大深さは、左部分木と右部分木のうち深い方の深さに1を加えたものです。

// 最小深さの計算
func minDepth(_ node: BinaryNode?) -> Int {
    guard let currentNode = node else { return 0 }
    if currentNode.leftChild == nil && currentNode.rightChild == nil { return 1 }
    if currentNode.leftChild == nil { return minDepth(currentNode.rightChild) + 1 }
    if currentNode.rightChild == nil { return minDepth(currentNode.leftChild) + 1 }
    return min(minDepth(currentNode.leftChild), minDepth(currentNode.rightChild)) + 1
}

最小深さは、根から最も近い葉までの距離を表します。

// 平衡二分木の判定
func isBalanced(_ node: BinaryNode?) -> Bool {
    guard let currentNode = node else { return true }
    let leftHeight = height(node: currentNode.leftChild)
    let rightHeight = height(node: currentNode.rightChild)
    if abs(leftHeight - rightHeight) > 1 { return false }
    return isBalanced(currentNode.leftChild) && isBalanced(currentNode.rightChild)
}

func height(node: BinaryNode?) -> Int {
    guard let currentNode = node else { return 0 }
    return max(height(node: currentNode.leftChild), height(node: currentNode.rightChild)) + 1
}

平衡二分木とは、任意のノードについてその左右の部分木の高さ差が1以下であることを指します。

// 二分木の直径計算
class BinaryTreeDiameter {
    private var maxLength = 0
    
    func calculateDiameter(_ root: BinaryNode?) -> Int {
        calculateHeight(root)
        return maxLength
    }
    
    private func calculateHeight(_ node: BinaryNode?) -> Int {
        guard let currentNode = node else { return 0 }
        let leftHeight = calculateHeight(currentNode.leftChild)
        let rightHeight = calculateHeight(currentNode.rightChild)
        maxLength = max(maxLength, leftHeight + rightHeight)
        return max(leftHeight, rightHeight) + 1
    }
}

二分木の直径は、任意の2つのノード間のパス長における最大値を指します。