有一棵有个节点的二叉树,其根节点为。修剪规则如下:
1.修剪掉当前二叉树的叶子节点,但是不能直接删除叶子节点
2.只能修剪叶子节点的父节点,修剪了父节点之后,叶子节点也会对应删掉
3.如果想在留下尽可能多的节点前提下,修剪掉所有的叶子节点。请你返回修剪后的二叉树。
有如下二叉树:
o / \ o o / \ / \ o o o o
修剪过后仅会留下根节点。
o / \ o o / \ / \ o o o o
{1,1,1,1,1,1,1}
{1}
叶子节点为最下面的4个1节点,但是不能直接修剪,只能修剪中间的2个1,修剪掉之后,只有根节点了
{1,#,1,#,1,#,1,#,1}
{1,#,1,#,1}
退化为一条链了,将最后两个节点删除。
,删除根节点时返回为空。
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 }