树的基本操作-526互联

class TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val
    this.left = left === undefined ? null : left
    this.right = right === undefined ? null : right
  }
}

/**
 * 数组转二叉树
 *     - 树 -> 递归（深度优先遍历）、队列（广度优先遍历）
 *     - 二叉树 -> 前序遍历、中序遍历（二叉搜索树）、后序遍历
 * @param array
 */
function arrayToBinaryTree(array: (number | null)[]): TreeNode | null {
  const arrayNode: TreeNode[] = []
  for (let i = 0; i < array.length; i++) {
    arrayNode.push(new TreeNode(array[i] || 0, null, null))
  }
  for (let i = 0; i < arrayNode.length; i++) {
    if (arrayNode[2 * i + 1]) {
      arrayNode[i].left = arrayNode[2 * i + 1]
      arrayNode[i].right = arrayNode[2 * i + 2]
    } else {
      break
    }
  }
  return arrayNode[0]
}

/**
 * 递归遍历
 * @param root
 */
function recursionErgodic(root: TreeNode | null): void {
  if (root) {
    // console.log(root.val) // 前序遍历
    recursionErgodic(root.left)
    console.log(root.val) // 中序遍历
    recursionErgodic(root.right)
    // console.log(root.val) // 后序遍历
  }
}

/**
 * 队列遍历
 * @param root
 */
function queueErgodic(root: TreeNode | null): void {
  const queue: TreeNode[] = []
  if (root) {
    queue.push(root)
  }
  while (queue.length) {
    const node = queue.shift()!
    console.log(node.val)
    if (node.left) {
      queue.push(node.left)
    }
    if (node.right) {
      queue.push(node.right)
    }
  }
}

const treeNode = arrayToBinaryTree([
  8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15
])
recursionErgodic(treeNode)
console.log('****************')
queueErgodic(treeNode)