面试算法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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35