1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public TreeNode pruneTree(TreeNode root) {
if (root == null) {
return null;
}
boolean containsOne = helper(root);
return containsOne ? root : null;
}
private boolean helper(TreeNode node) {
if (node == null) {
return true;
}
if (!helper(node.left)) {
node.left = null;
}
if (!helper(node.right)) {
node.right = null;
}
return node.left != null || node.right != null || node.val == 1;
}
}
|
递归函数的功能就是告诉我们一个tree是否有1以及把该tree中没有1的subtree给嘎了.
时间复杂度: O(n)
空间复杂度: O(n)
1
2
3
4
5
6
7
8
9
10
| class Solution {
public TreeNode pruneTree(TreeNode root) {
if (root == null) {
return null;
}
root.left = pruneTree(root.left);
root.right = pruneTree(root.right);
return root.val == 0 && root.left == null && root.right == null ? null : root;
}
}
|
第二种写法. 递归函数的功能就是给定一个树, 把该嘎的都嘎完然后返回这个处理好的树.
时间复杂度: O(n)
空间复杂度: O(n)
