题目主要信息

1、给一个n个节点的二叉树

2、不可以直接删除叶节点，只能修改叶节点的父节点

3、保留尽可能多的节点

方法一:递归遍历方法

具体方法

为了保留尽可能多的树节点，采用贪心的方式，只删除所有叶结点的父节点。

对于一个要删除的节点，它的特点是，存在有为叶节点的子节点。我们通过遍历树，判断该节点的子节点是否需要删除，如果需要删除，则置为null，即可删除。

Java代码

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return TreeNode类
     */
    public TreeNode pruneLeaves (TreeNode root) {
        // write code here
        if(root == null || needPrune(root)){
            return null;
        }
        visit(root);
        return root;
    }
    public void visit(TreeNode node){
        if(node==null){
            return;
        }
        if(node.left!=null && needPrune(node.left)){  //判断左节点是否需要删除
            node.left = null;
        }else{
            visit(node.left);
        }
        if(node.right!=null && needPrune(node.right)){  //判断右节点是否需要删除
            node.right = null;
        }else{
            visit(node.right);
        }
    }
    public boolean isLeaf(TreeNode node){
        if(node == null){
            return false;
        }
        if(node.left==null && node.right==null){
            return true;
        }
        else{
            return false;
        }
    }
    public boolean needPrune(TreeNode node){
        if(node.left!=null && isLeaf(node.left)){
            return true;
        }
        if(node.right!=null && isLeaf(node.right)){
            return true;
        }
        return false;
    }
}

复杂度分析

• 时间复杂度：$O(N)O(N)$，遍历整棵树，N为树的节点数
• 空间复杂度：平均空间复杂度$O(logN)O(logN)$，最坏时间复杂度$O(N)O(N)$，递归深度为树的深度

方法二：递归删除实现

具体方法

这一题我们也可以通过递归的方式实现。pruneLeaves函数返回的是修剪后的树节点，通过递归方式，分别对左节点和右节点进行修剪。

对于修剪的判定，依然是采取判断子节点是否为叶节点的方式。

Java代码

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return TreeNode类
     */
    public TreeNode pruneLeaves (TreeNode root) {
        if(root == null)
            return null;
        if(root.left != null && isLeaf(root.left))  //判断该节点左节点是否为叶节点，如果是，该节点需要删除
            return null;
        if(root.right != null && isLeaf(root.right))  //判断该节点右节点是否为叶节点，如果是，该节点需要删除
            return null;
        root.left = pruneLeaves(root.left);
        root.right = pruneLeaves(root.right);
        return root;
    }
    public boolean isLeaf(TreeNode node){
      return node!=null && (node.left == null && node.right == null )
    }
}

复杂度分析

• 时间复杂度：$O(N)O(N)$，递归访问整棵树，N为树的节点数
• 空间复杂度：平均时间复杂度$O(logN)O(logN)$，最坏时间复杂度$O(N)O(N)$，递归深度为树的深度