修剪叶子

[编程题]修剪叶子

热度指数：3261 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

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，点此查看相关信息

算法知识视频讲解

Python3

liangzhengjie

# 可以先标记，在剪除

# 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)

Python3

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)