递归、搜索与回溯算法:⼆叉树中的深搜-例题三

解法(dfs - 后序遍历):
后序遍历按照左⼦树、右⼦树、根节点的顺序遍历⼆叉树的所有节点,通常⽤于⽗节点的状态依赖于⼦节点状态的题⽬。
算法思路:
如果我们选择从上往下删除,我们需要收集左右⼦树的信息,这可能导致代码编写相对困难。然⽽,通过观察我们可以发现,如果我们先删除最底部的叶⼦节点,然后再处理删除后的节点,最终的结果并不会受到影响。
因此,我们可以采⽤后序遍历的⽅式来解决这个问题。在后序遍历中,我们先处理左⼦树,然后处理右⼦树,最后再处理当前节点。在处理当前节点时,我们可以判断其是否为叶⼦节点且其值是否为 0,如果满⾜条件,我们可以删除当前节点。
需要注意的是,在删除叶⼦节点时,其⽗节点很可能会成为新的叶⼦节点。因此,在处理完⼦节点后,我们仍然需要处理当前节点。这也是为什么选择后序遍历的原因(后序遍历⾸先遍历到的⼀定是叶⼦节点)。
通过使⽤后序遍历,我们可以逐步删除叶⼦节点,并且保证删除后的节点仍然满⾜删除操作的要
求。这样,我们可以较为⽅便地实现删除操作,⽽不会影响最终的结果。
若在处理结束后所有叶⼦节点的值均为 1,则所有⼦树均包含 1,此时可以返回。
算法流程:
递归函数设计:void dfs(TreeNode*& root)
1. 返回值:⽆;
2. 参数 :当前需要处理的节点;
3. 函数作⽤:判断当前节点是否需要删除,若需要删除,则删除当前节点。
后序遍历的主要流程:
1. 递归出⼝:当传⼊节点为空时,不做任何处理;
2. 递归处理左⼦树;
3. 递归处理右⼦树;
4. 处理当前节点:判断该节点是否为叶⼦节点(即左右⼦节点均被删除,当前节点成为叶⼦节点), 并且节点的值为 0:
a. 如果是,就删除掉;
b. 如果不是,就不做任何处理。
上一篇:【51单片机入门记录】A/D、D/A转换器PCF859应用


下一篇:uniapp Android 开发手机模拟器调试接口出现 Failed to connect to localhost/127.0.0.1:9999