题目
一棵二叉树的所有节点的值要么是0要么是1,请剪除该二叉树中所有节点的值全都是0的子树。例如,在剪除图8.2(a)中二叉树中所有节点值都为0的子树之后的结果如图8.2(b)所示。
分析
下面总结什么样的节点可以被删除。首先,这个节点的值应该是0。其次,如果它有子树,那么它的子树的所有节点的值都为0。也就是说,如果一个节点可以被删除,那么它的子树的所有节点都可以被删除。文章来源:https://www.toymoban.com/news/detail-736303.html
由此发现,后序遍历最适合用来解决这个问题。如果用后序遍历的顺序遍历到某个节点,那么它的左右子树的节点一定已经遍历过了。每遍历到一个节点,就要确定它是否有左右子树,如果左右子树都是空的,并且节点的值是0,那么也就可以删除这个节点。文章来源地址https://www.toymoban.com/news/detail-736303.html
解
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;
}
}
到了这里,关于面试算法47:二叉树剪枝的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!