深度遍历(DFS)

  1. // 递归的方式
  2. function DFS(root) {
  3.   let res = []
  4.     if (root === null) return []
  5.   root.left && res.push(...DFS(root.left))
  6.   root.right && res.push(...DFS(root.right))
  7.   return res
  8. }
  10. // 非递归方式
  11. function DFS(root) {
  12.   if (root === null) return []
  13.   var res = []
  14.   var stack = []
  15.   stack.push(root); 
  16.   while(stack.length) {
  17.        var item = stack.pop();
  18.      res.push(item)
  19.         if (item.left) stack.push(item.right) // 先放右边再放左边，这样一会pop会先出left
  20.         if (item.left) stack.push(item.left) // 
  21.   }
  22.   return res
  23. }

广度遍历(BFS)

  1. let result = [];
  2. let stack = [tree]; // 先将要遍历的树压入栈
  3. let count = 0; // 用来记录执行到第一层
  4. function bfs (root) {
  5.     let node = stack[count]
  6.   if (node) {
  7.        result.push(node)
  8.      if(node.left) stack.push(node.left);
  9.      if(node.right) stack.push(node.right);
  10.     count++
  11.     bfs()
  12.   }
  13. }
  14. bfs();
  17. // 非递归写法
  19. function bfs(node) {
  20.     let res = []
  21.   let queue = [node]
  22.   let point = 0
  23.   while (point < queue.length) {
  24.     let item = queue[point++]
  25.       res.push(item)
  26.     if (item.left) queue.push(item)
  27.     if (item.right) queue.push(item)
  28.   }
  29.   return res
  30. }
  32. bfs(tree)