。

这个算法会尽可能深的搜索树或者图的分支#xff0c;直到⼀条路径上的所有节点都被遍历

完毕#xff0c;然后再回溯到上…

⼀种遍历算法。

这个算法会尽可能深的搜索树或者图的分支直到⼀条路径上的所有节点都被遍历

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

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

并且前中后序三种遍历的唯⼀区别就是访问根节点的时机不同在做题的时候选择⼀个适当的遍历顺序对于算法的理解是非常有帮助的。

1.题目描述

evaluateTree(root-right);return

root-val

通过前序遍历往左右子树传递信息并且在回溯时得到左右子树的返回值。

让递归函数完成两件事

将父节点的数字与当前节点的信息整合到⼀起计算出当前节点的数字然后传递到下⼀层进行递归

当遇到叶子节点的时候就不再向下传递信息将整合的结果向上⼀直回溯到根节点。

递归函数设计int

函数作用整合父节点的信息与当前节点的信息计算当前节点数字并向下传递再回溯时返回当前子树当前节点作为子树根节点数字和。

我们画图来理解一下,举个例子:

如果我们选择从上往下删除我们需要收集左右⼦树的信息这可能导致代码编写相对困难。

然而

通过观察我们可以发现如果我们先删除最底部的叶子节点然后再处理删除后的节点最终的结果并不会受到影响。

因此我们可以采⽤后序遍历的方式来解决这个问题。

在后序遍历中我们先处理左子树然后处理

右子树最后再处理当前节点。

在处理当前节点时我们可以判断其是否为叶子节点且其值是否为

需要注意的是在删除叶子节点时其父节点很可能会成为新的叶子节点。

因此在处理完子节点后我们仍然需要处理当前节点。

这也是为什么选择后序遍历的原因后序遍历⾸先遍历到的一定是叶子节点。

通过使用后序遍历我们可以逐步删除叶子节点并且保证删除后的节点仍然满足删除操作的要

若在处

处理当前节点判断该节点是否为叶⼦节点即左右⼦节点均被删除当前节点成为叶子节点

3.代码实现:

pruneTree(root-left);root-right

pruneTree(root-right);if(root-left

nullptr

如果一棵树是二叉搜索树那么它的中序遍历的结果一定是⼀个严格递增的序列。

因此我们可以初始化⼀个无穷小的全区变量用来记录中序遍历过程中的前驱结点。

那么就可以在中序遍历的过程中先判断是否和前驱结点构成递增序列然后修改前驱结点为当前结点传入下一层的递归中。

算法流程