题解 | #修剪叶子#

修剪叶子

题目描述

有一棵有n个节点的二叉树，其根节点为root。修剪规则如下:

1.修剪掉当前二叉树的叶子节点，但是不能直接删除叶子节点

2.只能修剪叶子节点的父节点，修剪了父节点之后，叶子节点也会对应删掉

3.如果想在留下尽可能多的节点前提下，修剪掉所有的叶子节点。请你返回修剪后的二叉树。

方法一：贪心方法

解题思路

对于本题目的求解，利用贪心的思想，为了保留尽可能多的节点，只删除所有叶节点的父节点。

解题代码

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; // 叶子节点，返回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;
    }
}

复杂度分析

时间复杂度：遍历整棵树，节点为N，因此时间复杂度为$O(N)O(N)$。

空间复杂度：考虑到递归调用栈深度，因此空间复杂度为$O(logN)O(logN)$，最坏情况树变成链表，此时空间复杂度为$O(N)O(N)$。

方法二：递归方法

解题思路

对于本题目的求解，可以用递归的方式进行求解，分别对当前节点的子节点进行修建。对于修剪的判断，即判断子节点是否为叶节点的父节点。

解题代码

import java.util.*;

public class Solution {
  
    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){
        if(node.left == null && node.right == null)
        {
            return true;
        }else
        {
            return false;
        }
    }
}

复杂度分析

时间复杂度：递归访问整棵树，树节点为N，因此时间复杂度为$O(N)O(N)$。

空间复杂度：递归深度为树的深度，因此空间复杂度为$O(logN)O(logN)$，但如果遇到最坏情况，二叉树转换成链表，则空间复杂度为$O(N)O(N)$