1. Construct a binary tree

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init(_ val: Int=0._ left: TreeNode?=nil._ right: TreeNode?=nil) {
      self.val = val
      self.left = left
      self.right = right
    }
}
Copy the code

Traversal the binary tree

2.1 Prior traversal (root-left-right)

func preorderTraversal ( _ root: TreeNode?).- > [Int] {
    var r : [Int] = []
    if(root?.val = = nil) {
        return[]}else {
        r.append(root!.val)
        r.append(contentsOf: preorderTraversal(root!.left))
        r.append(contentsOf: preorderTraversal(root!.right))
        return r
    }
}
Copy the code

2.2 Middle order Traversal (left-root-right)

func middenTraversal ( _ root: TreeNode?).- > [Int] {
    var r : [Int] = []
    if(root?.val = = nil) {
        return[]}else {
        r.append(contentsOf: middenTraversal(root?.left))
        r.append(root!.val)
        r.append(contentsOf: middenTraversal(root?.right))
        return r
    }
}
Copy the code

2.3 Post-order Traversal (left-right-root)

func postorderTraversal ( _ root: TreeNode?).- > [Int] {
    var r : [Int] = []
    if(root?.val = = nil) {
        return[]}else {
        r.append(contentsOf: postorderTraversal(root?.left))
        r.append(contentsOf: postorderTraversal(root?.right))
        r.append(root!.val)
        return r
    }
}
Copy the code

2.4 Sequence traversal (traversal of root nodes layer by layer)

func levelOrder ( _ root: TreeNode?).- > [[Int]] {
    // write code here
    var res = [[Int]] ()if root = = nil {
        return res
    }
    var queue = [root!] // Define a TreeNode queue to operate on later
    while !queue.isEmpty { 
      // If the TreeNode is not empty, the queue will be traversed. The first TreeNode is root, the second TreeNode will be two, the third TreeNode will be four, and so on
        let r = getNodes(queue)
        res.append(r.vals)
        queue = r.nodes
    }
    return res
}

// Get val at each level and node at the next level
func getNodes(_ nodes: [TreeNode]) -> (vals: [Int], nodes: [TreeNode]) {
    var values = [Int] ()var nextNodes = [TreeNode] ()for treeNode in nodes {
        values.append(treeNode.val)
        if let l = treeNode.left {
            nextNodes.append(l)
        }
        if let r = treeNode.right {
            nextNodes.append(r)
        }
    }
    return (values, nextNodes)
}
Copy the code

The traversal order of binary tree is relative to the root node. The root in front is in front order, the root in middle is in middle order, and the root in back is in back order

Third, the characteristic judgment of binary tree

3.1. Find the maximum depth of the binary tree

Depth refers to the number of nodes along the path from the root node of the tree to any leaf node. Maximum depth is the maximum depth of all leaf nodes.

func maxDepth ( _ root: TreeNode?). -> Int {
    // write code here
    if(root?.val = = nil) {
        return 0
    }
    return 1 + max(maxDepth(root?.left),maxDepth(root?.right))
}
Copy the code

3.2 a path in the binary tree and whether there is a certain value

Given a binary tree root and a value sum, determine whether the sum of the values of the nodes from root to leaf is equal to sum

Simplify to whether there is a sum-root.val value in the left and right subtrees, and then solve recursively

func hasPathSum ( _ root: TreeNode? ._ sum: Int) -> Bool {
    // write code here
    if root = = nil {
        return false
    }
    if root?.left = = nil && root?.right = = nil && sum - root!.val = = 0 {
        return true
    }
    return hasPathSum(root?.left, sum-root!.val) || hasPathSum(root?.right, sum-root!.val)
}
Copy the code

3.3. Is the binary tree symmetric

Whether the left and right subtrees are symmetric

func isSymmetrical ( _ pRoot: TreeNode?). -> Bool {
    // write code here
    if pRoot = = nil {
        return true
    }
    return isSame(pRoot?.left, pRoot?.right)
}

func isSame(_ leftTreeNode: TreeNode? ._ rightTreeNode: TreeNode?). -> Bool {
    if leftTreeNode = = nil && rightTreeNode = = nil {
        return true
    }
    if leftTreeNode = = nil || rightTreeNode = = nil {
        return false
    }
    return leftTreeNode?.val = = rightTreeNode?.val && isSame(leftTreeNode?.left, rightTreeNode?.right) && isSame(leftTreeNode?.right, rightTreeNode?.left)
}
Copy the code

3.4. Merge binary trees

Merge two binary trees, nodes that both exist, add up the values of the nodes, otherwise the empty space is replaced by a node of the other tree

func mergeTrees ( _ t1: TreeNode? ._ t2: TreeNode?). -> TreeNode? {
    // write code here
    if t1 = = nil {
        return t2
    }
    if t2 = = nil {
        return t1
    }
    return TreeNode(t1!.val+t2!.val, mergeTrees(t1?.left, t2?.left), mergeTrees(t1?.right, t2?.right))
}
Copy the code

3.5. Mirror image of binary tree

Operates on the given binary tree to transform it into a mirror image of the source binary tree.

func Mirror ( _ pRoot: TreeNode?). -> TreeNode? {
    // write code here
    if pRoot = = nil {
        return nil
    }
    return TreeNode(pRoot!.val, Mirror(pRoot?.right), Mirror(pRoot?.left))
}
Copy the code

Four,

  1. Binary tree problems generally consider empty first, then the root node processing, and then the left and right subtrees
  2. The left and right subtrees are binary trees, so the problems of binary trees are generally handled by recursion
  3. We use recursion for binary tree problems
  4. recursive
  5. recursive
  6. recursive