# 814     Binary Tree Pruning

## 814. [Binary Tree Pruning](https://leetcode.com/problems/binary-tree-pruning/description/)

## 1. Question

We are given the head node`root` 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.)

```
Example 1:
Input:
 1
  \ 
   0 
  / \
 0   1

Output: 

 1
  \
   0
    \
     1

Explanation:

Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.
```

## 2. Implementation

**(1) DFS**

思路: post order traversal, 先处理左子树和右子树，然后如果当前node是leaf且它的值为0的话，把该node删除

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode pruneTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if (root.left == null && root.right == null && root.val == 0) {
            return null;
        }
        return root;
    }
}
```

## 3. Time & Space Complexity

DFS: 时间复杂度O(n), 空间复杂度: O(h)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/oj-practices/chapter1/tree/814-binary-tree-pruning.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.