DFS

  1. // 所有遍历函数的入参都是树的根结点对象
  2. function preorder(root) {
  3.     // 递归边界，root 为空
  4.     if(!root) {
  5.         return 
  6.     }
  8.     // 输出当前遍历的结点值
  9.     console.log('当前遍历的结点值是：', root.val)  
  10.     // 递归遍历左子树 
  11.     preorder(root.left)  
  12.     // 递归遍历右子树  
  13.     preorder(root.right)
  14. }

BFS

  1. function BFS(root) {
  2.     const queue = [] // 初始化队列queue
  3.     // 根结点首先入队
  4.     queue.push(root)
  5.     // 队列不为空，说明没有遍历完全
  6.     while(queue.length) {
  7.         const top = queue[0] // 取出队头元素  
  8.         // 访问 top
  9.         console.log(top.val)
  10.         // 如果左子树存在，左子树入队
  11.         if(top.left) {
  12.             queue.push(top.left)
  13.         }
  14.         // 如果右子树存在，右子树入队
  15.         if(top.right) {
  16.             queue.push(top.right)
  17.         }
  18.         queue.shift() // 访问完毕，队头元素出队
  19.     }
  20. }