学习数据结构——二叉树

虽然我在工作中从没有用到过二叉树这个结构，但是觉得还是挺重要的。emmm，就是这样。

二叉树：二叉树的每个节点最多有两个子节点，一般称为左子节点和右子节点，二叉树有左子树和右子树之分。

节点实现

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

二叉树是由递归实现的，所以理论上所有的二叉树问题都可以通过递归的方法来实现。
计算二叉树最大深度

func maxDepth(_ root: TreeNode?) -> Int {
    guard let root = root else { return 0 }
    return max(maxDepth(root.left), maxDepth(root.right)) + 1
}

判断一棵二叉树是否二叉查找树(二叉查找树：所有左子树节点的值都小于根节点的值，所有右子树节点的值都大于根节点的值)

func isValidBST(_ root: TreeNode?) -> Bool{
    
    return helper(root, nil, nil)
}

func helper(_ node: TreeNode?, _ min: Int?, _ max:Int?) -> Bool{
    guard let node = node else {
        return true
    }
    if let min = min, node.val <= min {
        return false
    }
    if let max = max, node.val >= max{
        return false
    }
    return helper(node.left, min, node.val) && helper(node.right, node.val, max)
}

翻转一颗二叉树

func invertTree(_ root: TreeNode?) -> TreeNode? {
    if root == nil {
        return nil
    }
    let left = invertTree(root?.left)
    let right = invertTree(root?.right)
    
    root?.left = right
    root?.right = left
    return root
}

两棵二叉树求和

func MergeTree(_ t1: TreeNode?, _ t2: TreeNode?) -> TreeNode? {
    if (t1 == nil || t2 == nil) {return t1 == nil ? t2 : t1}
    let val = t1!.val + t2!.val
    let root = TreeNode(val)
    root.left = MergeTree(t1?.left, t2?.left)
    root.right = MergeTree(t1?.right, t2?.right)
    
    return root
}

递归遍历二叉树

func printTree(treeNode:TreeNode?) -> Int {
    if treeNode == nil {
        return 0
    }
    print(treeNode?.val as Any)
    printTree(treeNode: treeNode?.left)
    printTree(treeNode: treeNode?.right)
    return 1
}

非递归遍历二叉树（用栈实现前序遍历）
思路：用栈来存放二叉树的节点， 节点的左子树为空时删除该节点并将父节点的右子树添加进栈

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 cenOrderTraversal(root: TreeNode?) -> [Int] {
    var res = [Int]()
    var stack = [TreeNode]()
    var node = root
    
    while !stack.isEmpty || node != nil {
        if node != nil {
            stack.append(node!)
            node = node!.left
        } else {
            node = stack.removeLast()
            res.append(node!.val)
            node = node?.right
        }
    }
    
    return res
}

层级遍历二叉树

func levelOrder(root: TreeNode?) -> [[Int]] {
    var res = [[Int]]()
    var queue = [TreeNode]()
    
    if let root = root {
        queue.append(root)
    }
    
    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
    
}

链接如下：
故胤道长_二叉树讲解