Swift- Common binary tree operations

The definition of binary tree

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}}Copy the code

Comparison of binary trees

Binary trees are equal

Comparing whether two binary trees are equal or not is also a common function in binary tree operations. The main idea is to use backtracking to compare nodes of binary trees one by one. The code is as follows:

func isSameTree(_ p: TreeNode? ._ q: TreeNode?). -> Bool {
    if p = = nil && q = = nil {
        return true
    }
    if p ! = nil && q ! = nil && p?.val = = q?.val {
        return isSameTree(p?.left, q?.left) && isSameTree(p?.right, q?.right)
    } else {
        return false}}Copy the code

Symmetric binary tree decision

func isSymmetric(_ root: TreeNode?). -> Bool {
    
    return isMirror(root, t2: root)
}

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

The maximum depth of a binary tree

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

Minimum depth of binary tree

// Minimum depth of binary tree
func minDepth(_ root: TreeNode?). -> Int {
    if root = = nil {
        return 0
    }
    let leftH = minDepth(root?.left)
    let rightH = minDepth(root?.right)
    if leftH ! = 0 && rightH ! = 0 {
        return min(leftH, rightH) + 1
    } else {
        return leftH + rightH + 1}}Copy the code

Binary tree path synthesis

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

Balanced binary tree judgment

// Balance the binary tree
func isBalanced(_ root: TreeNode?). -> Bool {
    return dfsHeight(root) ! = -1
}

func dfsHeight(_ root: TreeNode?). -> Int {
    if root = = nil {
        return 0
    }
    let leftHeight = dfsHeight(root?.left)
    if leftHeight = = -1 {
        return -1
    }
    let rightHeight = dfsHeight(root?.right)
    if rightHeight = = -1 {
        return -1
    }
    if abs(leftHeight - rightHeight) > 1 {
        return -1
    }
    return max(leftHeight, rightHeight) + 1
}
Copy the code

Binary Search tree (BST)

Binary sort tree (BST) is called binary search tree or binary sort tree. BST satisfies the following three conditions:

• The left subtree of a node contains a node whose value is less than that node’s value
• The right subtree of a node contains a node whose value is greater than or equal to that node’s value
• The left and right subtrees of the node are both BST
• Middle order traversal can produce an increasing sequence

Check whether the binary tree is BST

func isValidBST(root: TreeNode?). -> Bool {
    return _helper(node: 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: node.left, min, node.val) && _helper(node: node.right, node.val, max)
}
Copy the code

Define a binary search tree

public class BinarySearchTree<T: Comparable> {
    private(set) public var value: T
    private(set) public var parent: BinarySearchTree?
    private(set) public var left: BinarySearchTree?
    private(set) public var right: BinarySearchTree?
    
    public init(value: T) {
        self.value = value
    }
    /// Is the root node
    public var isRoot: Bool {
        return parent = = nil
    }
    /// is a leaf node
    public var isLeaf: Bool {
        return left = = nil && right = = nil
    }
    /// is the left child node
    public var isLeftChild: Bool {
        return parent?.left = = = self
    }
    /// is the right child node
    public var isRightChild: Bool {
        return parent?.right = = = self
    }
    /// Whether there is a left child node
    public var hasLeftChild: Bool {
        return left ! = nil
    }
    /// Whether there is a right child node
    public var hasRightChild: Bool {
        return right ! = nil
    }
    /// Whether there are child nodes
    public var hasAnyChild: Bool {
        return hasLeftChild || hasRightChild
    }
    // whether there are two child nodes
    public var hasBothChildren: Bool {
        return hasLeftChild && hasRightChild
    }
    /// The current node includes the total number of nodes in the subtree
    public var count: Int {
        return (left?.count ?? 0) + 1 + (right?.count ?? 0)}}Copy the code

Basic operation

Insert a new node

When we perform the insert, we first compare the new value to the root node. If the new value is small, we take the left branch; If it’s bigger, we take the right branch. We go down this path until we find a space where we can insert a new value.

public func insert(value: T) {
      if value < self.value {
          if let left = left {
              left.insert(value: value)
          } else {
              left = BinarySearchTree(value: value)
              left?.parent = self}}else {
          if let right = right {
              right.insert(value: value)
          } else {
              right = BinarySearchTree(value: value)
              right?.parent = self}}}Copy the code

The creation of BST

Create binary lookup numbers as arrays:

public convenience init(array: [T]) {
  	precondition(array.count > 0)
  	self.init(value: array.first!)
  	for v in array.dropFirst() {
    		insert(value: v)
  	}
}
Copy the code

Search binary search tree

• If the value is less than the current node, the left branch is selected.
• If the value is greater than the current node, the right branch is selected.
• If the value is equal to the current node, we have found it!

public func search(value: T) -> BinarySearchTree? {
  	if value < self.value {
    	return left?.search(value)
  	} else if value > self.value {
    	return right?.search(value)
  	} else {
    	return self  // found it!}}Copy the code

Traverse the binary search tree

There are three ways to traverse a binary tree:

• Middle-order (or depth-first, in-order /depth-first) : First look at the left child of the node, then look at the node itself, and finally look at its right child.
• Pre-order: First look at the node itself, then look at its left and right children.
• Post-order: First look at the left and right child nodes and last process the node itself.

The process of traversing the tree is also recursive; if you traverse the binary search tree in middle order, it looks at all the nodes and the results are ordered.

// middle order traversal
public func traverseInOrder(process: (T) - >Void) {
  	left?.traverseInOrder(process: process)
  	process(value)
  	right?.traverseInOrder(process: process)
}
// preorder traversal
public func traversePreOrder(process: (T) - >Void) {
  	process(value)
  	left?.traversePreOrder(process: process)
  	right?.traversePreOrder(process: process)
}
// after the sequence traversal
public func traversePostOrder(process: (T) - >Void) {
  	left?.traversePostOrder(process: process)
  	right?.traversePostOrder(process: process)
  	process(value)
}
Copy the code

Remove nodes

After deleting a binary search tree node, replace it with the largest child node on the left or the smallest node on the right.

// Remove a node
@discardableResult public func remove(a) -> BinarySearchTree? {
  	let replacement: BinarySearchTree?

  	// The replacement of the current node can be the largest replacement on the left or
  	// The smallest on the right
  	if let right = right {
    	replacement = right.minimum()
  	} else if let left = left {
    	replacement = left.maximum()
  	} else {
    	replacement = nil
  	}

  	replacement?.remove()

  	// Place the replacement at the current node's location
    replacement?.right = right
    replacement?.left = left
    right?.parent = replacement
    left?.parent = replacement
    reconnectParentTo(node:replacement)

    // The current node is no longer part of the tree, so clean it up.
    parent = nil
    left = nil
    right = nil

    return replacement
}
// Reset a node
private func reconnectParentTo(node: BinarySearchTree?). {
  	if let parent = parent {
    	if isLeftChild {
      	parent.left = node
    	} else {
      	parent.right = node
    	}
  	}
  	node?.parent = parent
}
Copy the code

Converts an ordered array to a binary lookup tree

public func sortedArrayToBST(_ nums: [Int]) -> BinarySearchTree<Int>? {
      if nums.isEmpty {
          return nil
      }

      return sortedArrayToBSTFunc(nums, l: 0, r: nums.count-1)}// Convert an ordered array to a binary search tree
  private func sortedArrayToBSTFunc(_ nums: [Int].l: Int.r: Int) -> BinarySearchTree<Int>? {
      if r < l {
          return nil
      }
      let mid = l + (r - l) / 2
      let root = BinarySearchTree<Int>(value: nums[mid])
      root.left = sortedArrayToBSTFunc(nums, l: l, r: mid-1)
      root.right = sortedArrayToBSTFunc(nums, l: mid+1, r: r)
      return root
  }
Copy the code