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/