颖灵信息科技网站建设,学seo需要多久,05网电子书,公司手机版网站制作题目
一棵二叉树的所有节点的值要么是0要么是1#xff0c;请剪除该二叉树中所有节点的值全都是0的子树。例如#xff0c;在剪除图8.2#xff08;a#xff09;中二叉树中所有节点值都为0的子树之后的结果如图8.2#xff08;b#xff09;所示。
分析
下面总结什么样的节…题目
一棵二叉树的所有节点的值要么是0要么是1请剪除该二叉树中所有节点的值全都是0的子树。例如在剪除图8.2a中二叉树中所有节点值都为0的子树之后的结果如图8.2b所示。
分析
下面总结什么样的节点可以被删除。首先这个节点的值应该是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;}
}
