二叉树的bfs和dfs

0. 动机:很多问题都要用到树的遍历;

1. 二叉树的方式:dfs(3种:先中后序)和bfs(层序);

2. bfs和dfs时间复杂度区别:全部是O(n);

3. bfs和dfs空间复杂度区别:

  • bfs:O(w),w为??的最大宽度,高度为h(从0计算)的树最大宽度2h,此时为O(n/2);
  • dfs:O(h),h为??的最大高度,平衡二叉树是O(logn),最坏情况,偏斜二叉树是O(n);
  • 所以bfs和dfs,最坏情况的空间开销都是O(n);
  • 当树更平衡时,bfs的空间开销可能更大,当树偏斜时,dfs的空间开销可能更大;

4. 选择哪一种遍历方式的考虑:

  • 空间开销
  • dfs一般是递归实现,需要函数调用开销
  • bfs是从根开始遍历,dfs一般是从叶节点开始遍历,所以看问题需求

 

参考链接:https://www.geeksforgeeks.org/bfs-vs-dfs-binary-tree/

 

二叉树的bfs和dfs

上一篇:如何查看当前电脑上的Maven版本呢?


下一篇:《网络安全体系结构》一1.1 网络安全是一个系统