面试算法47：二叉树剪枝

题目

一棵二叉树的所有节点的值要么是0要么是1，请剪除该二叉树中所有节点的值全都是0的子树。例如，在剪除图8.2（a）中二叉树中所有节点值都为0的子树之后的结果如图8.2（b）所示。

分析

下面总结什么样的节点可以被删除。首先，这个节点的值应该是0。其次，如果它有子树，那么它的子树的所有节点的值都为0。也就是说，如果一个节点可以被删除，那么它的子树的所有节点都可以被删除。

由此发现，后序遍历最适合用来解决这个问题。如果用后序遍历的顺序遍历到某个节点，那么它的左右子树的节点一定已经遍历过了。每遍历到一个节点，就要确定它是否有左右子树，如果左右子树都是空的，并且节点的值是0，那么也就可以删除这个节点。

解

public class Test {public static void main(String[] args) {TreeNode node1 = new TreeNode(1);TreeNode node0 = new TreeNode(0);TreeNode node00 = new TreeNode(00);TreeNode node000 = new TreeNode(000);TreeNode node0000 = new TreeNode(0000);TreeNode node00000 = new TreeNode(00000);TreeNode node11 = new TreeNode(1);node1.left = node0;node1.right = node00;node0.left = node000;node0.right = node0000;node00.left = node00000;node00.right = node11;TreeNode result = pruneTree(node1);System.out.println(result);}public static TreeNode pruneTree(TreeNode root) {if (root == null) {return root;}root.left = pruneTree(root.left);root.right = pruneTree(root.right);if (root.left == null && root.right == null && root.val == 0) {return null;}return root;}
}