深度优先遍历DFS全称为DepthFirstTraversal是我们树或者图这样的数据结构中常⽤的⼀种***遍历算法***。

这个算法会尽可能深的搜索树或者图的分⽀直到⼀条路径上的所有节点都被遍历完毕然后再回溯到上⼀层继续找⼀条路遍历。

在⼆叉树中常⻅的深度优先遍历为前序遍历、中序遍历以及后序遍历。

因为树的定义本⾝就是递归定义因此采⽤递归的⽅法去实现树的三种遍历不仅容易理解⽽且代码很简洁。

并且前中后序三种遍历的唯⼀区别就是

***访问根节点的时机不同***在做题的时候选择⼀个适当的遍历顺序对于算法的理解是⾮常有帮助的。

题目介绍

叶⼦节点要么值为0要么值为1其中0表⽰False1表⽰True。

⾮叶⼦节点要么值为2要么值为3其中2表⽰逻辑或OR3表⽰逻辑与AND。

如果节点是个叶⼦节点那么节点的值为它本⾝即True或者False。

否则计算两个孩⼦的节点值然后将该节点的运算符对两个孩⼦值进⾏运算。

算法思路

当问题的规模变为n1时即叶⼦节点的值为0或1我们可以直接获取当前节点值为0或1。

递归函数流程

通过***判断当前节点的逻辑运算符***计算左右⼦节点值运算得出的结果

代码如下

{if(root-leftnullptr||root-rightnullptr){return

root-val;}else{if(root-val2)return

evaluateTree(root-left)||evaluateTree(root-right);elsereturn

evaluateTree(root-left)evaluateTree(root-right);}}

};2.

给你⼀个⼆叉树的根节点root树中每个节点都存放有⼀个0到9之间的数字。

解题思路

前序遍历按照根节点、左⼦树、右⼦树的顺序遍历⼆叉树的所有节点通常⽤于

往左右⼦树传递信息并且在回溯时得到左右⼦树的返回值。

递归函数可以帮我们完成两件事

将⽗节点的数字与当前节点的信息整合到⼀起计算出当前节点的数字然后传递到下⼀层进⾏递归当遇到叶⼦节点的时候就***不再向下传递信息***⽽是

***将整合的结果向上⼀直回溯到根节点***。

在递归结束时根节点需要返回的值也就被更新为了整棵树的数字和。

递归函数流程

结合⽗节点传下的信息以及当前节点的val计算出当前节点数字sum

如果当前结点不是叶⼦节点将sum传到左右⼦树中去得到左右⼦树中节点路径的数字和然后

代码如下

x;else{xx*10root-val;}if(root-left!nullptrroot-right!nullptr)return

sumNumber(root-left,x)sumNumber(root-right,x);else

sumNumber(root-right,x);elsereturn

x;}

给你⼆叉树的根结点root此外树的每个结点的值要么是0要么是1。

解法dfs-后序遍历

后序遍历按照左⼦树、右⼦树、根节点的顺序遍历⼆叉树的所有节点通常⽤于

递归出⼝当传⼊节点为空时不做任何处理

处理当前节点判断该节点是否为叶⼦节点即左右⼦节点均被删除,前点成为叶⼦节点并且节点的值为0

代码如下

{dfs(root);if(root-leftnullptrroot-rightnullptrroot-val0)return

nullptr;elsereturn

{if(root-leftnullptrroot-rightnullptr)return

root-val;bool

上述解法不仅使⽤⼤量额外空间存储数据并且会将所有的结点都遍历⼀遍。

因此我们可以创建⼀个全局的计数器***count***将其初始化为***k***每遍历⼀个节点就将***count–***。

直到某次递归的时候count的值等于0说明此时的结点就是我们要找的结果。

代码如下

};好啦递归问题就讲到这里下一次讲解的是搜索回溯和全排列我们下次再见