题解

二叉树后序遍历的应用，每个结点遍历一次，时间复杂度O(n)，空间复杂度O(1)

代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pruneTree(root *TreeNode) *TreeNode {
    rootSum := prune(root)
    if rootSum == 0{
        return nil
    }
    return root
}

func prune(root *TreeNode) int {
    sum := (*root).Val
    if (*root).Left != nil{
        val := prune((*root).Left)
        if val == 0{
            (*root).Left = nil
        }else{
            sum += val
        }
    }
    if (*root).Right != nil{
        val := prune((*root).Right)
        if val == 0{
            (*root).Right = nil
        }else{
            sum += val
        }
    }
    return sum
}

跑分