2.手写JavaScript广度和深度优先遍历二叉树

一、核心思想：

1.深度遍历：

依靠栈先进后出的机制，分别设置返回结果的数组和栈数组，首先判断栈非空，对每个结点，将其出栈并把值push到结果数组，判断是否有右左孩子，分别将其加入栈中，循环执行上述操作。否则返回结果数组。

2.广度遍历：

依靠队列先进先出的机制，分别设置返回结果的数组和队列数组，首先判断队列非空，对每个结点，将其出队列并把值push到结果数组，判断是否有左右孩子，分别将其加入队列中，循环执行上述操作。否则返回结果数组。

二、代码实现：

1.深度遍历：

let tree = {
  val: 1,
  leftChild: {
    val: 2,
    leftChild: {
      val: 3,
      leftChild: {
        val: 4,
      },
      rightChild: {
        val: 5,
      },
    },
    rightChild: {
      val: 6,
    },
  },
  rightChild: {
    val: 7,
    leftChild: {
      val: 8,
    },
    rightChild: {
      val: 9,
      leftChild: {
        val: 10,
      },
    },
  },
};
/**
 * 深度遍历二叉树
 * @param {Array} root 传入数组
 * @return {Array} 返回深度遍历二叉树数组结果
 */
function deepTree(root) {
  let list = [],
  stack = [root];
  while (stack.length) {
    let target;
    target = stack.pop();
    list.push(target.val)
    if (target.rightChild) {
      stack.push(target.rightChild)
    }
    if (target.leftChild) {
      stack.push(target.leftChild)
    }
  }
  return list
}
console.log(deepTree(tree));
// [
//   1, 2, 3, 4,  5,
//   6, 7, 8, 9, 10
// ]

2.广度遍历

let tree = {
  val: 1,
  leftChild: {
    val: 2,
    leftChild: {
      val: 3,
      leftChild: {
        val: 4,
      },
      rightChild: {
        val: 5,
      },
    },
    rightChild: {
      val: 6,
    },
  },
  rightChild: {
    val: 7,
    leftChild: {
      val: 8,
    },
    rightChild: {
      val: 9,
      leftChild: {
        val: 10,
      },
    },
  },
};
/**
 * 广度遍历二叉树
 * @param {Array} root 传入数组
 * @return {Array} list 返回深度遍历二叉树数组结果
 */
function broadTree(root) {
  let list = [],
    queue = [root];
  while (queue.length) {
    let target = queue.shift();
    list.push(target.val);
    if (target.leftChild) {
      queue.push(target.leftChild);
    }
    if (target.rightChild) {
      queue.push(target.rightChild);
    }
  }
  return list;
}
console.log(broadTree(tree))
// [
//   1, 2, 7, 3,  6,
//   8, 9, 4, 5, 10
// ]