解决方案


方法:递归

思路

trim(node) 作为该节点上的子树的理想答案。我们可以递归地构建该答案。

算法

,那么修剪后的二叉树必定出现在节点的左边。类似地,当 ,那么修剪后的二叉树出现在节点的右边。否则,我们将会修剪树的两边。

复杂度分析

  • 时间复杂度:,其中 是给定的树的全部节点。我们最多访问每个节点一次。

  • 空间复杂度:。即使我们没有明确使用任何额外的内存,在最糟糕的情况下,我们递归调用的栈可能与节点数一样大。