//
//  Algorithm.swift
//  galaxy
//
//  Created by edy on 2023/12/29.
//

import UIKit

class Node<T> {
    
    var value: T
    var next: Node<T>?
    init(value: T, next: Node<T>? = nil) {
        self.value = value
        self.next = next
    }
}
    
struct LinkList<T>: CustomStringConvertible {
    
    var head: Node<T>?
    var tail: Node<T>?
    var isEmpty: Bool {
        head == nil
    }
    
    var description: String {
        var desc = ""
        var node = head
        while node != nil {
            desc += "\(node!.value)->"
            node = node!.next
        }
        
        desc += "head:\(head?.value) tail:\(tail?.value)"
        return desc
    }
    
    mutating func push(_ value: T) {
        // 此乃头插法
        head = Node(value: value, next: head)
        if tail == nil {
            tail = head
        }
    }
    
    mutating func append(_ value: T) {
        // 此乃尾插法
        let node = Node(value: value)
        tail?.next = node
        tail = node
        if head == nil {
            head = node
        }
    }
    
    mutating func pop() -> T? {
        // 此乃头删法
        // defer 所声明的 block 会在当前代码执行return退出后被调用
        defer {
            head = head?.next
            if isEmpty {
                tail = nil
            }
        }
        return head?.value
        
    }
    
    mutating func removeLast() -> T? {
        // 此乃尾删法
        // 头结点为空直接返回
        guard let head = head else {return nil}
        // 只有一个节点
        guard let _ = head.next else {return pop()}
        // 以下情况是链表有不小于2个节点的case
        
        var currentNode = head
        var previousNode = head
        
        while let next = currentNode.next {
            previousNode = currentNode
            currentNode = next
        }
        
        previousNode.next = nil
        tail = previousNode
        return currentNode.value
    }
    
    // 反转链表 (非递归)
    mutating func reveseLinkList() -> LinkList<T> {
        guard let _ = head else { return self }
        guard let _ = head?.next else { return self }
        
        // 以下情况是链表有不小于2个节点的case
        var previous: Node<T>?
        var current = head
        
        tail = head
        
        while current != nil {
            let next = current?.next
            current?.next = previous
            previous = current
            current = next
        }
        
        head = previous
        return self
    }
    
    mutating func rr() {
        tail = head
        head = reverse(head)
    }
    
    // 反转链表（递归）
    mutating func reverse(_ node: Node<T>?) -> Node<T>? {
         
        if node == nil || node?.next == nil { return node }
        let newHead = reverse(node?.next)
        node?.next?.next = node
        node?.next = nil
        return newHead
     }
}

class TreeNode<T> {
    var value: T
    var left: TreeNode<T>?
    var right: TreeNode<T>?
    
    init(value: T, left: TreeNode<T>? = nil, right: TreeNode<T>? = nil) {
        self.value = value
        self.left = left
        self.right = right
    }
    
    // 翻转树
    func reverseBinaryTree(_ node: TreeNode?) -> TreeNode? {
        guard let _ = node else { return node}
        var leftNode = node?.left
        node?.left = reverseBinaryTree(node?.right)
        node?.right = reverseBinaryTree(leftNode)
        return node
    }
    
    //  求二叉树的节点个数
    func getTreeNodeNum(_ node: TreeNode<T>?) -> Int {
        if node == nil { return 0 }
        return getTreeNodeNum(node?.left) + getTreeNodeNum(node?.right) + 1
    }
    
    // 二叉树的最小深度
    func getMinDepth(_ node: TreeNode<T>?) -> Int {
        if node == nil { return 0 }
        
        let leftMin = getMinDepth(node!.left)
        let rightMin = getMinDepth(node!.right)
        // 此处很精髓
        if node!.left == nil || node!.right == nil { return leftMin+rightMin+1 }
        return  min(leftMin, rightMin) + 1
    }
    
    // 二叉树的最大深度
    func getMaxDepth(_ node: TreeNode<T>?) -> Int {
        if node == nil { return 0 }
        // 此处注意和求最小深度的差别
        return max(getMaxDepth(node?.left), getMaxDepth(node?.right)) + 1
    }
    
    // 归并树
    func mergeBinaryTree(_ left: TreeNode<Int>?, _ right: TreeNode<Int>?) -> TreeNode<Int>? {
        
            if left == nil {
                return right
            }

            if right == nil {
                return left
            }
            
        var mergeNode = TreeNode<Int>(value: (left!.value + right!.value))
            mergeNode.left = mergeBinaryTree(left!.left, right!.left)
            mergeNode.right = mergeBinaryTree(left!.right, right!.right)

            return mergeNode
    }
}
