算法现学现卖—— 递归 and DFS

作者:杨润炜
日期:2020/4/25 11:29

递归 and DFS

简述

  • 要了解DFS,首先要了解递归,它一般用来解决重复性问题,而且形式十分简洁,比如树的遍历、DFS。
  • DFS字面上的意思也就是它的实际意义和主要应用场景,深度优先搜索。运行的过程就像是遍历树的过程,每一次从根节点出发,遍历完子树再回到父节点,递归重复这个过程就可以遍历完整棵树,也就完成了深度优先搜索。

有两个比较形象的方式理解递归:

  • 想必大家都看过《盗梦空间》吧(没有的就有借口看看啦),可以把递归的过程想象成盗梦空间里进入别人梦境的过程,每一层的环境都是独立的,而且主角可以通过探到下一层把信息带到上层;
  • 另外一个是生活中看电影的场景,如果你在看电影的时候想知道自己坐在第几排(假设电影院里太黑,大家都看不到座位号,哈哈),这时你可以问你前一排,前一排再问他的前一排,一直到第一排(第一排没有前排了,所以自然知道自己在第一排),就回复说自己在第一排,然后第二排也知道了,反方向将信息传递回来,每一层都知道了自己的排号,直到传到最上层。我们把向下问的过程叫“递”,把回复的过程叫“归”。

我们以二叉树的前序遍历为例,展示深度优先搜索的递归过程,如下图:

代码模板

递归形式,利用系统给我们维护的栈

  1. dfs (level, params):
  2. # 递归终止条件
  3. if level >= max_level:
  4. return
  5. do_something()
  6. # 下探到下一层
  7. dfs(level + 1, params)

自定义栈

  1. while stack:
  2. # 栈顶元素出栈
  3. current_node = stack.pop()
  4. do_something()
  5. # 将子节点入栈
  6. if current_node.child:
  7. stack.append(current_node.child)

LeetCode题目

N叉树的前序遍历
N叉树的后序遍历
括号生成

感谢您的阅读!
如果看完后有任何疑问,欢迎拍砖。
欢迎转载,转载请注明出处:http://www.yangrunwei.com/a/105.html
邮箱:glowrypauky@gmail.com
QQ: 892413924