LeetCode二叉树的前序遍历、中序遍历、后序遍历、层序遍历、最大深度Swift

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    var res:[Int] = []
    func preorderTraversal(_ root: TreeNode?) -> [Int] {
        if root == nil {return []}
        res.append(root!.val)
        preorderTraversal(root!.left)
        preorderTraversal(root!.right)  
        return res
    }
}

概念

前序遍历：根节点-左子树-右子树

class Solution {
    var res:[Int] = []
    func preorderTraversal(_ root: TreeNode?) -> [Int] {
        if root == nil {return []}
        res.append(root!.val)
        preorderTraversal(root!.left)
        preorderTraversal(root!.right)  
        return res
    }
}

中序遍历：左子树-根节点-右子树

class Solution {
    var res:[Int] = []
    func inorderTraversal(_ root: TreeNode?) -> [Int] {
        if root == nil {return []}
        inorderTraversal(root!.left)
        res.append(root!.val)
        inorderTraversal(root!.right)  
        return res
    }
}

后序遍历：左子树-右子树-根节点

class Solution {
    var res:[Int] = []
    func postorderTraversal(_ root: TreeNode?) -> [Int] {
        if root == nil {return []}
        postorderTraversal(root!.left)
        postorderTraversal(root!.right)  
        res.append(root!.val)
        return res
    }
}

层序遍历：一层一层遍历

思路一：利用两个数组，遍历二叉树，先把根节点加进根节点数组中，把他的左右子结点加进下一级结点数组中。然后清空根节点数组，将下一级结点数组当做根节点数组，依次迭代。

class Solution {
    
    func levelOrder(_ root: TreeNode?) -> [[Int]] {
        guard let root = root else { return [] }
        //最终结果数组
        var result:[[Int]] = []
        //根节点数组
        var rootArr:[TreeNode] = [root]
        //下一级节点数组
        var nextLevelArr:[TreeNode] = []
        while !rootArr.isEmpty {
            //存放根节点值得数组
            var tmpArr:[Int] = []
            for node in rootArr {
                //把根节点数组里的值放进去临时数组
                tmpArr.append(node.val)
                if let node = node.left {
                    nextLevelArr.append(node)
                }
                if let node = node.right {
                    nextLevelArr.append(node)
                }
            }
            //把临时数组放进最终结果数组
            result.append(tmpArr)
            rootArr.removeAll()
            rootArr=nextLevelArr
            nextLevelArr.removeAll()
        }
        return result
    }
}

思路二：利用队列先进先出的原理，遍历二叉树，先把父节点加进去，然后移除父节点，把他的左右子节点加进去。

class Solution {
    func levelOrder(_ root: TreeNode?) -> [[Int]] {
        guard let root = root else { return [] }
        //最终结果数组
        var result:[[Int]] = []
        //根节点数组
        var queue:[TreeNode] = [root]
        while !queue.isEmpty {
            //存放根节点值得数组
            var tmpArr:[Int] = []
            for node in queue {
                //把根节点数组里的值放进去临时数组
                tmpArr.append(node.val)
                queue.removeFirst()
                if let node = node.left {
                    queue.append(node)
                }
                if let node = node.right {
                    queue.append(node)
                }
            }
            //把临时数组放进最终结果数组
            result.append(tmpArr)
        }
        return result
    }
}

深度优先遍历：

前序遍历：ABDECFG

中序遍历：DBEAFCG

后序遍历：DEBFGCA

广度优先遍历：

层序遍历：ABCDEFG

二叉树的最大深度

思路一：层序遍历总层数

class Solution {
    func maxDepth(_ root: TreeNode?) -> Int {
        guard let root = root else { return 0 }
        //根节点数组
        var queue:[TreeNode] = [root]
        var depth = 0
        while !queue.isEmpty {
            for node in queue {
                queue.removeFirst()
                if let node = node.left {
                    queue.append(node)
                }
                if let node = node.right {
                    queue.append(node)
                }
            }
            depth+=1
        }
        return depth
    }
}

思路二：二叉树的最大深度=Max(左子树的最大深度，右子树的最大深度)+1

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