binary-tree-pruning

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given the <code>root</code> of a binary tree, return the same tree where every subtree (of the given tree) not containing a <code>1</code> has been removed.

A subtree of a node <code>node</code> is <code>node</code> plus every node that is a descendant of <code>node</code>.

&nbsp;
Example 1:
<img alt="" src="https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/06/1028_2.png" style="width: 500px; height: 140px;" />
<pre>
Input: root = [1,null,0,0,1]
Output: [1,null,0,null,1]
Explanation: 
Only the red nodes satisfy the property &quot;every subtree not containing a 1&quot;.
The diagram on the right represents the answer.
</pre>

Example 2:
<img alt="" src="https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/06/1028_1.png" style="width: 500px; height: 115px;" />
<pre>
Input: root = [1,0,1,0,0,0,1]
Output: [1,null,1,null,1]
</pre>

Example 3:
<img alt="" src="https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/05/1028.png" style="width: 500px; height: 134px;" />
<pre>
Input: root = [1,1,0,1,1,0,1,0]
Output: [1,1,0,1,1,null,1]
</pre>

&nbsp;
Constraints:

<ul>
	<li>The number of nodes in the tree is in the range <code>[1, 200]</code>.</li>
	<li><code>Node.val</code> is either <code>0</code> or <code>1</code>.</li>
</ul>

pruneTree

Binary Tree Pruning

Tree

Depth-First Search

Binary Tree

给你二叉树的根结点&nbsp;<code>root</code>&nbsp;，此外树的每个结点的值要么是 <code>0</code> ，要么是 <code>1</code> 。

返回移除了所有不包含 <code>1</code> 的子树的原二叉树。

节点 <code>node</code> 的子树为 <code>node</code> 本身加上所有 <code>node</code> 的后代。

&nbsp;

示例 1：
<img alt="" src="https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/06/1028_2.png" style="width: 500px; height: 140px;" />
<pre>
输入：root = [1,null,0,0,1]
输出：[1,null,0,null,1]
解释：
只有红色节点满足条件“所有不包含 1 的子树”。 右图为返回的答案。
</pre>

示例 2：
<img alt="" src="https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/06/1028_1.png" style="width: 500px; height: 115px;" />
<pre>
输入：root = [1,0,1,0,0,0,1]
输出：[1,null,1,null,1]
</pre>

示例 3：
<img alt="" src="https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/05/1028.png" style="width: 500px; height: 134px;" />
<pre>
输入：root = [1,1,0,1,1,0,1,0]
输出：[1,1,0,1,1,null,1]
</pre>

&nbsp;

提示：

<ul>
	<li>树中节点的数目在范围 <code>[1, 200]</code> 内</li>
	<li><code>Node.val</code> 为 <code>0</code> 或 <code>1</code></li>
</ul>