binary-tree-pruning

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

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

&#32473;&#20320;&#20108;&#21449;&#26641;&#30340;&#26681;&#32467;&#28857;&nbsp;<code>root</code>&nbsp;&#65292;&#27492;&#22806;&#26641;&#30340;&#27599;&#20010;&#32467;&#28857;&#30340;&#20540;&#35201;&#20040;&#26159; <code>0</code> &#65292;&#35201;&#20040;&#26159; <code>1</code> &#12290;

&#36820;&#22238;&#31227;&#38500;&#20102;&#25152;&#26377;&#19981;&#21253;&#21547; <code>1</code> &#30340;&#23376;&#26641;&#30340;&#21407;&#20108;&#21449;&#26641;&#12290;

&#33410;&#28857; <code>node</code> &#30340;&#23376;&#26641;&#20026; <code>node</code> &#26412;&#36523;&#21152;&#19978;&#25152;&#26377; <code>node</code> &#30340;&#21518;&#20195;&#12290;

&nbsp;

&#31034;&#20363; 1&#65306;
<img alt="" src="https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/06/1028_2.png" style="width: 500px; height: 140px;" />
<pre>
&#36755;&#20837;&#65306;root = [1,null,0,0,1]
&#36755;&#20986;&#65306;[1,null,0,null,1]
&#35299;&#37322;&#65306;
&#21482;&#26377;&#32418;&#33394;&#33410;&#28857;&#28385;&#36275;&#26465;&#20214;&ldquo;&#25152;&#26377;&#19981;&#21253;&#21547; 1 &#30340;&#23376;&#26641;&rdquo;&#12290; &#21491;&#22270;&#20026;&#36820;&#22238;&#30340;&#31572;&#26696;&#12290;
</pre>

&#31034;&#20363; 2&#65306;
<img alt="" src="https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/06/1028_1.png" style="width: 500px; height: 115px;" />
<pre>
&#36755;&#20837;&#65306;root = [1,0,1,0,0,0,1]
&#36755;&#20986;&#65306;[1,null,1,null,1]
</pre>

&#31034;&#20363; 3&#65306;
<img alt="" src="https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/05/1028.png" style="width: 500px; height: 134px;" />
<pre>
&#36755;&#20837;&#65306;root = [1,1,0,1,1,0,1,0]
&#36755;&#20986;&#65306;[1,1,0,1,1,null,1]
</pre>

&nbsp;

&#25552;&#31034;&#65306;

<ul>
	<li>&#26641;&#20013;&#33410;&#28857;&#30340;&#25968;&#30446;&#22312;&#33539;&#22260; <code>[1, 200]</code> &#20869;</li>
	<li><code>Node.val</code> &#20026; <code>0</code> &#25110; <code>1</code></li>
</ul>

Sunbelt Computer Software

PL/B Language Development and Support