有一棵有
个节点的二叉树，其根节点为
。修剪规则如下:
1.修剪掉当前二叉树的叶子节点，但是不能直接删除叶子节点
2.只能修剪叶子节点的父节点，修剪了父节点之后，叶子节点也会对应删掉
3.如果想在留下尽可能多的节点前提下，修剪掉所有的叶子节点。请你返回修剪后的二叉树。
有如下二叉树:
o
/ \
o o
/ \ / \
o o o o 修剪过后仅会留下根节点。
[编程题]修剪叶子
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)
递归就行
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)
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)
常规解法略，这里给一下其他其他解法的一些思路，仅供参考
>>. 求出最小深度，直接递归判断是否已达到裁剪要求
① 层序遍历法：
public static TreeNode pruneLeaves(TreeNode root) {
// write code here
if (minDepth(root) < 3) return null;
root.left = pruneLeaves(root.left);
root.right = pruneLeaves(root.right);
return root;
}
// 根节点不能为叶子结点
public static int minDepth(TreeNode root) {
// 层序遍历
Deque<TreeNode> queue = new ArrayDeque<>();
if (root != null) {
if (root.left != null)
queue.add(root.left);
if (root.right != null)
queue.add(root.right);
}
if (queue.isEmpty()) return 1;
int minDepth = 1;
while (!queue.isEmpty()) {
boolean isLeaf = false;
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode curNode = queue.poll();
assert curNode != null;
if (curNode.left != null) queue.offer(curNode.left);
if (curNode.right != null) queue.offer(curNode.right);
if (curNode.left == null && curNode.right == null) {
isLeaf = true;
break;
}
}
minDepth++;
if (isLeaf) return minDepth;
}
return minDepth;
}v ② 直接 DFS 遍历求最小深度
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 static TreeNode pruneLeaves(TreeNode root) {
// write code here
if (minDepth(root) < 3) return null;
if (root.left != null) root.left = pruneLeaves(root.left);
if (root.right != null) root.right = pruneLeaves(root.right);
return root;
}
public static int minDepth(TreeNode root) {
if (root == null)
return Integer.MAX_VALUE;
if (root.left == null && root.right == null)
return 1;
return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}
}
发表于 2024-07-15 12:06:12
回复(0)
# 可以先标记，在剪除
# 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: TreeNode) -> TreeNode: # write code here mark = set() self.traverse(root, mark) if root in mark: return None self.cut(root, mark) return root def traverse(self, root, mark): if root is None: return False if root.left is None and root.right is None: mark.add(root) return True if self.traverse(root.left, mark): mark.add(root) return False if self.traverse(root.right, mark): mark.add(root) return False return False def cut(self, root, mark): if root is None: return if root in mark: return if root.left in mark: root.left = None self.cut(root.left, mark) if root.right in mark: root.right = None self.cut(root.right, mark)
发表于 2024-05-23 23:10:23
回复(0)
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)
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)
递归写不好 写的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)
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)
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)
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)
遇到对树的操作时，大部分时候需要使用递归
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)
问题信息
通过挑战的用户
查看代码-
2023-03-13 15:27:50
-
2023-02-16 23:07:04 -
2022-12-17 15:45:11 -
2022-11-25 15:37:18
-
2022-11-14 09:38:36
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
