二叉树剪枝_二叉树遍历与剪枝

目前工作中遇到如下问题，对象之间有依赖关系，抽象来看作一棵二叉树，最上层的是root节点，而父节点会依赖子节点。如果现在有一些节点已经标记为无效，我们要删除这些无效节点。如果无效节点的依赖的节点还有效，那么不应该删除，如果无效节点和它的子节点都无效，则可以删除。

如下图所示

看到这个问题，第一个想法就是递归，而二叉树的递归有:前序遍历，中序遍历和后序遍历。

最开始我只是确定要递归，根本就没有考虑什么顺序，我的流程如下：

public TreeNode pruneTree (TreeNode root) {

if (root.val ==

0 && root.left.val == 0 && root.right.val ==0) {

return null;

}

root.left

= pruneTree(root.left);

root.right

= pruneTree(root.right);

}

这里看到一个明显的异常的情况是

因此剪枝只能从叶子节点开始遍历，然后再遍历父节点，这样才能保证每次剪枝是逐级剪去无用的节点，到父节点的时候无用的节点都已经去掉，只需要判断当前节点和它的子节点是否为0就可以了。这个时候我明白，和二叉树的遍历顺序有关系。

在递归里面前序，中序和后序代表的遍历顺序和处理逻辑的顺序如下：

前序遍历

public TreeNode pruneTree (TreeNode root) {

//前序

doSomeThing();

root.left =

pruneTree(root.left);

root.right

= pruneTree(root.right);

}

中序遍历

public TreeNode pruneTree (TreeNode root) {

root.left =

pruneTree(root.left);

//中序

doSomeThing();

root.right

= pruneTree(root.right);

}

后续遍历

public TreeNode pruneTree (TreeNode root) {

root.left =

pruneTree(root.left);

root.right

= pruneTree(root.right);

//后续

doSomeThing();

}

上面递归中不通的顺序就代表了不同的遍历顺序，同时代表了不同的实现，在二叉树遍历过程中要注意不同遍历顺序的要求。