修剪叶子

[编程题]修剪叶子

热度指数：2889 时间限制：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，点此查看相关信息

算法知识视频讲解

Java

牛客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)