定义

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init(_ val: Int) {
        self.val = val
    }
}

深度

// 获取深度
func maxDepth(root: TreeNode?) -> Int {
    guard let root = root else { return 0 }
    
    // 获取左子树、右子树深度的最大值，再加1就是当前树的深度
    return max(maxDepth(root: root.left), maxDepth(root: root.right)) + 1
}

二叉查找树

它是一种特殊的二叉树。它的特点就是左子树中节点的值都小于根节点的值，右子树中节点的值都大于根节点的值。

// 是否是二叉查找树
func isValidBST(root: TreeNode?) -> Bool {
    return helper(root: root, min: nil, max: nil)
}

// 辅助函数，比较当前节点的值是否大于min，小于max
func helper(root: TreeNode?, min: Int?, max: Int?) -> Bool {
    guard let node = root else { return true }
    
    // 如果min不为空并且当前节点的值小于等于min返回false
    if let min = min, node.val <= min {
        return false
    }
    
    // max不为空并且当前节点的值大于max返回false
    if let max = max, node.val >= max {
        return false
    }
    
    // 递归调用，分别比较当前节点的左子节点的值是否小于当前节点的值以及当前节点的右子节点的值是否大于当前节点的值
    return helper(root: node.left, min: min, max: node.val) && helper(root: node.right, min: node.val, max: max)
}

遍历

最常见的树的遍历有三种，前序、中序、后序遍历。这三种写法相似，无非是递归的顺序略有不同。

// 前序遍历
func preorder(root: TreeNode?, result: inout [Int]) {
    guard let node = root else { return }
    
    result.append(node.val)
    preorder(root:node.left , result: &result)
    preorder(root:node.right , result: &result)
}

// 使用栈来前序遍历
func preorderTraversal(root: TreeNode?) -> [Int] {
    var res = [Int]()
    var stack = [TreeNode]()
    var node = root
    
    // 使用栈来缓存遍历过的左子树节点，然后从最大深度开始出栈
    while !stack.isEmpty || node != nil {
        if node != nil {
            res.append(node!.val)
            stack.append(node!)
            node = node!.left
        } else {
            node = stack.removeLast().right
        }
    }
    return res
}

前序遍历的顺序

// 使用队列来实现树的层级遍历
func levelOrder(root: TreeNode?) -> [[Int]] {
    var res = [[Int]]()
    var queue = [TreeNode]()
    
    if let root = root {
        queue.append(root)
    }
    
    // 遍历queue中的节点
    while queue.count > 0 {
        let size = queue.count
        var level = [Int]()
        
        // 每次遍历过当前节点后就会把当前节点的子节点放入队列中，
        // 由于队列是先进先出的，这样就会按照这个顺序一个层级一个层级的往下执行
        for _ in 0..<size {
            let node = queue.removeFirst()
            
            level.append(node.val)
            if let left = node.left {
                queue.append(left)
            }
            if let right = node.right {
                queue.append(right)
            }
        }
        res.append(level)
    }
    
    return res
}

树的层级遍历

反转二叉树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
    func invertTree(_ root: TreeNode?) -> TreeNode? {
        guard let root = root else { return nil}
        
        root.left = invertTree(root.left)
        root.right = invertTree(root.right)
        
        var temp = root.left
        root.left = root.right
        root.right = temp
        
        return root
    }
}