首页 > 试题广场 >

修剪叶子

[编程题]修剪叶子
  • 热度指数：2866 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
有一棵有个节点的二叉树，其根节点为。修剪规则如下:
1.修剪掉当前二叉树的叶子节点，但是不能直接删除叶子节点
2.只能修剪叶子节点的父节点，修剪了父节点之后，叶子节点也会对应删掉
3.如果想在留下尽可能多的节点前提下，修剪掉所有的叶子节点。请你返回修剪后的二叉树。
有如下二叉树: 
     o
    / \
   o   o
  / \  / \
 o  o o   o
修剪过后仅会留下根节点。
示例1

输入

{1,1,1,1,1,1,1}

输出

{1}

说明

叶子节点为最下面的4个1节点，但是不能直接修剪，只能修剪中间的2个1，修剪掉之后，只有根节点了
示例2

输入

{1,#,1,#,1,#,1,#,1}

输出

{1,#,1,#,1}

说明

退化为一条链了，将最后两个节点删除。

备注:
，删除根节点时返回为空。

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
不偷不抢安度因_头像 不偷不抢安度因_ 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return TreeNode类
     */
    TreeNode* pruneLeaves(TreeNode* root) {
        // write code here
        if (root == nullptr) {
            return nullptr;
        }
        if (root->left == nullptr && root->right == nullptr) {
            return nullptr;
        }
        if (root->left != nullptr && root->left->left == nullptr && root->left->right == nullptr) {
            return nullptr;
        }
        if (root->right != nullptr && root->right->left == nullptr && root->right->right == nullptr) {
            return nullptr;
        }
        root->left = pruneLeaves(root->left);
        root->right = pruneLeaves(root->right);
        return root;
    }
};

发表于 2021-10-14 17:15:55 回复(0)
pein531头像 pein531
递归就行 
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 && 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;
    }
}

发表于 2021-10-26 21:38:15 回复(0)
tach1koma头像 tach1koma 
class Solution {
private:
    bool isLeaf(TreeNode *root) {
        return root && !root->left && !root->right;
    }
public:
    TreeNode* pruneLeaves(TreeNode* root) {
        if (!root || isLeaf(root) || isLeaf(root->left) || isLeaf(root->right))
            return nullptr;
        root->left = pruneLeaves(root->left);
        root->right = pruneLeaves(root->right);
        return root;
    }
};
发表于 2022-01-13 15:35:01 回复(0)
Python3
danspace头像 danspace 
class Solution:
    def pruneLeaves(self , root ):        
        def isLeaf(root):
            # 判断节点是否为叶子节点
            if root is not None and root.left is None and root.right is None:
                return True 
            return False 
        # 基础情况
        if root is None:
            return None 
        # 如果遇到叶子节点，则修剪父节点
        if isLeaf(root.left) or isLeaf(root.right):
            return None
        root.left = self.pruneLeaves(root.left)
        root.right = self.pruneLeaves(root.right)
        return root
发表于 2023-04-27 10:49:05 回复(0)
Go
小谷围做题家头像 小谷围做题家 
package main
import _"fmt"
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return TreeNode类
*/
func pruneLeaves( root *TreeNode ) *TreeNode {
    if check(root){
        return nil
    }
    if root.Left!=nil{
        if check(root.Left){
            root.Left=nil
        }else{
            pruneLeaves(root.Left)
        }
    }
    if root.Right!=nil{
        if check(root.Right){
            root.Right=nil
        }else{
            pruneLeaves(root.Right)
        }
    }
    return root
}

//检查是否叶子节点的父节点
func check(root *TreeNode)bool{
    if root.Left!=nil{
        if root.Left.Left==nil&&root.Left.Right==nil{
            return true
        }
    }
    if root.Right!=nil{
        if root.Right.Left==nil&&root.Right.Right==nil{
            return true
        }
    }
    return false
}

发表于 2023-03-07 17:59:26 回复(0)
Python
想去东北泡澡的共享单车人求你们别卷了头像 想去东北泡澡的共享单车人求你们别卷了
递归写不好 写的3次遍历 
1:    所有的叶节点值改为2
2:    所有叶节点的父节点值改为3
3:    所有值为3点节点改为None 

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return TreeNode类
#
class Solution:
    def pruneLeaves(self , root ):
        # write code here

        def find(tree):
            if not tree.right and not tree.left:
                tree.val = 2 
            if tree.right:
                find(tree.right)
            if tree.left:
                find(tree.left)

        find(root)

        def find2(tree):
            if tree.right:
                if tree.right.val == 2:
                    tree.val = 3 
                else:
                    find2(tree.right)
            if tree.left:
                if tree.left.val == 2:
                    tree.val = 3 
                else:
                    find2(tree.left)

        find2(root) 

        def find3(tree):
            if tree.right:
                if tree.right.val != 1:
                    tree.right = None 
                else:
                    find3(tree.right) 
            if tree.left:
                if tree.left.val != 1:
                    tree.left = None 
                else:
                    find3(tree.left) 
        find3(root) 
        if root.val == 2&nbs***bsp;root.val == 3:
            return None 
        return root


发表于 2022-12-16 17:25:20 回复(5)
不羁岁月hrl头像 不羁岁月hrl 
struct TreeNode*delete(struct TreeNode* root){
    if(!root) return root;
    if(root->left){
        if(root->left->left==NULL&&root->left->right==NULL) return NULL;
    }
    if(root->right){
        if(root->right->left==NULL&&root->right->right==NULL) return NULL;
    }
    root->left=delete(root->left);
    root->right=delete(root->right);
    return root;
}

struct TreeNode* pruneLeaves(struct TreeNode* root) {
    if(!root) return root;
    if(root->left==NULL&&root->right==NULL) return root;
    return delete(root);
}

发表于 2022-04-28 20:37:44 回复(0)
Java
牛客280397572号头像 牛客280397572号 
import java.util.*;

public class Solution {
    public TreeNode pruneLeaves (TreeNode root) {
        if (isLeaf(root.left) || isLeaf(root.right)) { 
            root = null;
            return null;
        }
        if (root.left != null) { root.left = pruneLeaves(root.left); }
        if (root.right != null) { root.right = pruneLeaves(root.right); }
        return root;
    }
    
    private boolean isLeaf (TreeNode root) {
        if (root == null) { return false; } 
        return root.left == null && root.right == null;
    }
}

发表于 2022-04-14 19:35:26 回复(0)
一切为了秋招头像 一切为了秋招 
TreeNode pruneLeaves(TreeNode root) { if (dfs(root)) return null; else return root;
} boolean dfs(TreeNode root) { if (root==null) return false; if (isLeaf(root.left)||isLeaf(root.right)) return true; boolean left=dfs(root.left); if (left) root.left=null; boolean right=dfs(root.right); if (right) root.right=null; return false;
} boolean isLeaf(TreeNode root) { return root!=null&&root.left==null&&root.right==null;
}
发表于 2022-04-06 15:44:21 回复(0)
Python 3
牛客505523419号头像 牛客505523419号 
class Solution():
    def findpath(self, node):
        if node is None:
            return None
        if node.left is None and node.right is not None:
            if node.right.left is None and node.right.right is None:
                return
        if node.right is None and node.left is not None:
            if node.left.left is None and node.left.right is None:
                return
        if node.left is not None and node.right is not None:
            if (node.left.left is None and node.left.right is None)&nbs***bsp;(node.right.left is None and node.right.right is None):
                return
        root = TreeNode(node.val)
        root.left = self.findpath(node.left)
        root.right = self.findpath(node.right)
        return root

发表于 2022-02-03 18:18:17 回复(0)
牛客59417909号头像 牛客59417909号
遇到对树的操作时，大部分时候需要使用递归
public classSolution {
    public TreeNode pruneLeaves (TreeNode root) {
        // write code here
        if(root==null) returnroot;
        if(root.left==null&&root.right==null) returnroot;
        root = cutleaves(root);
        return root;
    }
     
     public TreeNode cutleaves (TreeNode root) {
         if(root==null) returnroot;
         if(root.left!=null){
             if(root.left.left==null&&root.left.right==null)
                 returnnull;
         }
          if(root.right!=null){
             if(root.right.left==null&&root.right.right==null)
                 returnnull;
         }
         root.left = cutleaves(root.left);
        root.right = cutleaves(root.right);
         returnroot;
     }
}
发表于 2021-10-13 16:13:22 回复(0)
提交观点

问题信息

树
上传者：小小
难度：
11条回答 2616浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号