LeetCode第814题,难度中等
原题地址:https://leetcode-cn.com/problems/binary-tree-pruning/
题目描述:
给定二叉树根结点 root ,此外树的每个结点的值要么是 0,要么是 1。
返回移除了所有不包含 1 的子树的原二叉树。
( 节点 X 的子树为 X 本身,以及所有 X 的后代。)
示例1:
输入: [1,null,0,0,1]
输出: [1,null,0,null,1]
解释:
只有红色节点满足条件“所有不包含 1 的子树”。
右图为返回的答案。
示例2:
输入: [1,0,1,0,0,0,1]
输出: [1,null,1,null,1]
示例3:
输入: [1,1,0,1,1,0,1,0]
输出: [1,1,0,1,1,null,1]
说明:
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-tree-pruning
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路:
这题的思路是这样子的,递归判断根节点和它的左右子树是否符合要求。即首先调用hasOne(TreeNode)方法判断根节点及其子树是否有1,如果没有,那么就认为该树不符合要求,置为空;如果有1,那么就再接着判断左右子树是否符合要求。
中文官网题解:
https://leetcode-cn.com/problems/binary-tree-pruning/solution/
个人题解:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode pruneTree(TreeNode root) {
if (root == null) {
return null;
}
if (!hasOne(root)) {
return null;
}
root.left = pruneTree(root.left);
root.right = pruneTree(root.right);
return root;
}
private boolean hasOne(TreeNode root) {
if (root == null) {
return false;
}
if (root.val == 1) {
return true;
}
boolean has = hasOne(root.left);
if (has) {
return true;
} else {
return hasOne(root.right);
}
}
}
结果:
可以很明显的看到,大家全是0ms完成任务...