二叉树

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

二叉树的创建,给定一个数组[1,2,2,3,4,4,3]

二叉树一般解题思路是就是递归，从前序遍历（先根再左再右），中序遍历（先左再根再右），后序遍历（先左再右再根）

// 中序遍历
class Solution {
    func inorderTraversal(_ root: TreeNode?) -> [Int] {
        guard let root = root else { return []}
        return inorderTraversal(root.left) + [root.val] + inorderTraversal(root.right);
    }
}

// 前序遍历
class Solution {
    func inorderTraversal(_ root: TreeNode?) -> [Int] {
        guard let root = root else { return []}
        return [root.val]  + inorderTraversal(root.left) + ·  cinorderTraversal(root.right);
    }
}

比如求最大深度的

class Solution {
    func maxDepth(_ root: TreeNode?) -> Int {
        guard let root = root else { return 0}
      // 可以说是后序遍历/递归
        let max_left = maxDepth(root.left)
        let max_right = maxDepth(root.right)
        return max(max_left, max_right) + 1
    }
}

给定一个二叉树，检查它是否是镜像对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

class Solution {
    func isSymmetric(_ root: TreeNode?) -> Bool {
        guard let root = root else {return true}
        let value_left = isSymmetric(root.left) 
        let value_right = isSymmetric(root.right) 
        return value_left == true && value_right == true ? true : false
    }
}