814 Binary Tree Pruning
Last updated
Was this helpful?
Last updated
Was this helpful?
We are given the head noderoot
of a binary tree, where additionally every node's value is either a 0 or a 1.
Return the same tree where every subtree (of the given tree) not containing a 1 has been removed.
(Recall that the subtree of a node X is X, plus every node that is a descendant of X.)
(1) DFS
思路: post order traversal, 先处理左子树和右子树,然后如果当前node是leaf且它的值为0的话,把该node删除
DFS: 时间复杂度O(n), 空间复杂度: O(h)