

二叉树深搜的简单介绍

计算布尔二叉树的值
题目解析

算法原理
对于完全二叉树,一个节点要么都有左右孩子,或者为叶子节点。

如果我们要算一棵完全二叉树根节点的值,就要先算出这个根节点左子树的值以及右子树的值的整合结果,得到的结果和根节点的运算符再次进行整合,最终得到根节点的 boolean 结果。

解法:递归 DFS
函数头
根据上述算法原理,我们可以总结出函数头 boolean dfs(root)。
函数体
我们需要根据下面的三步来设计函数体:

所以可以总结函数体:
本文介绍二叉树深度优先搜索(DFS)算法,通过递归方式解决布尔二叉树求值和根到叶节点路径数字之和问题。阐述了递归出口设计、函数体逻辑及子任务分解方法,帮助读者理解二叉树遍历的核心思想。





对于完全二叉树,一个节点要么都有左右孩子,或者为叶子节点。

如果我们要算一棵完全二叉树根节点的值,就要先算出这个根节点左子树的值以及右子树的值的整合结果,得到的结果和根节点的运算符再次进行整合,最终得到根节点的 boolean 结果。

根据上述算法原理,我们可以总结出函数头 boolean dfs(root)。
我们需要根据下面的三步来设计函数体:

所以可以总结函数体:

微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML 转 Markdown 互为补充。 在线工具,Markdown 转 HTML在线工具,online
将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML 转 Markdown在线工具,online
通过删除不必要的空白来缩小和压缩JSON。 在线工具,JSON 压缩在线工具,online

我们只需要相信:dfs() 可以帮助我们完成整合所传入节点的最终结果即可。
在遍历到叶子节点时,只需要返回叶子节点值 true 或者 false 即可;这也是我们的递归出口。
注意:要根据每一个节点的 val,来决定返回的值是 true 或者 false。


我们之前说过,可以把 dfs 看作是一个黑盒,把要完成的任务放心交给它处理即可。但是如果 dfs 要处理的任务过多,是比较难叙述清楚的,这个时候我们该怎样解决呢?
我们根据如下完全二叉树来作为本题的例子,并且解决上述问题:

由题意可得:

在算出每条分支代表的数之后,我们需要根据算术方法,来总结出子问题,在递归到二叉树的每一层时,找出会重复执行的子任务;所以我们只关心递归到某一层时,会做的任务:

在递归到 5 节点时,需要执行的任务有两种:
拿到 8 和