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