题解 | #修剪叶子#
修剪叶子
http://www.nowcoder.com/practice/39b559fb84864bde93eccd6e87312650
题意：
方法一：
递归
思路：如果当前节点的左儿子或右儿子是叶子节点，则返回 null 。
否则，分别递归左儿子和右儿子。
最后返回 root 。
class Solution {
public:
TreeNode* pruneLeaves(TreeNode* root) {
if(root==nullptr)
return nullptr;
//左儿子节点是叶子节点
if(root->left&&root->left->left==nullptr&&root->left->right==nullptr){
return nullptr;
}
//右儿子节点是叶子节点
if(root->right&&root->right->left==nullptr&&root->right->right==nullptr){
return nullptr;
}
root->left=pruneLeaves(root->left);//递归左儿子节点
root->right=pruneLeaves(root->right);//递归右儿子节点
return root;
}
};
时间复杂度：%EF%BC%8C%E9%81%8D%E5%8E%86%E6%A0%91%E7%9A%84%E6%AF%8F%E4%B8%AA%E8%8A%82%E7%82%B9%E3%80%82)
空间复杂度：%EF%BC%8C%E6%9C%80%E5%9D%8F%E6%83%85%E5%86%B5%EF%BC%9A%E5%8D%95%E6%94%AF%E6%A0%91%EF%BC%8C%E9%81%8D%E5%8E%86%E6%A0%91%E7%9A%84%E6%AF%8F%E4%B8%AA%E8%8A%82%E7%82%B9%EF%BC%8C%E9%80%92%E5%BD%92%E6%A0%88%E5%A4%8D%E6%9D%82%E5%BA%A6%E6%98%AFO(n)%E3%80%82)
方法二：
java实现
思路：思路同方法一相同。
import java.util.*;
public class Solution {
public TreeNode pruneLeaves (TreeNode root) {
if(root==null){
return null;
}
//左儿子是叶子节点
if(root.left!=null&&root.left.left==null&&root.left.right==null){
return null;
}
//右儿子是叶子节点
if(root.right!=null&&root.right.left==null&&root.right.right==null){
return null;
}
root.left=pruneLeaves(root.left);//递归左儿子
root.right=pruneLeaves(root.right);//递归右儿子
return root;
}
}
时间复杂度：空间复杂度：
查看18道真题和解析
