###### tags: `Leetcode` `medium` `tree` `python`

# 814. Binary Tree Pruning

## [題目連結:]https://leetcode.com/problems/binary-tree-pruning/

## 題目:
Given the ```root``` of a binary tree, return the same tree where every subtree (of the given tree) not containing a ```1``` has been removed.

A subtree of a node ```node``` is ```node``` plus every node that is a descendant of ```node```.


#### [圖片來源:]https://leetcode.com/problems/binary-tree-pruning/

## 解題想法:
* 此題要求去除root中，所有由0構成的子樹
* 二元樹: 往遞歸思考
* 從尾一層層移除值為0的leaf node
* 初始判斷:
* 若node為空，即不存在，return None
* 對左右子遞歸
* 若左右子皆空，且該root.val==0
* 則移除此root，即return None
* 否則return root

## Python:

class TreeNode():
    def __init__ (self, val=0, left=None, right=None):
        self.val=val
        self.left=left
        self.right=right
    def InsertLeft(self,node):
        if not self.left:
            self.left=TreeNode(node)
        else:
            self.left.InsertLeft(node)
    def InsertRight(self,node):
        if not self.right:
            self.right=TreeNode(node)
        else:
            self.right.InsertRight(node)
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)

class Solution(object):
    def pruneTree(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: Optional[TreeNode]
        """
        if not root:
            return None
        root.left=self.pruneTree(root.left)
        root.right=self.pruneTree(root.right)
        #左右皆空且root.val==0
        if not root.left and not root.right and root.val==0:
            return None
        return root

if __name__=='__main__':
    root=TreeNode(1)
    root.InsertLeft(0)
    root.InsertRight(1)
    root.left.InsertLeft(0)
    root.left.InsertRight(0)
    root.right.InsertLeft(0)
    root.right.InsertRight(1)
    root.printTree()
    #[1, 0, 1, 0, 0, 0, 1]
    result=Solution()
    ans=result.pruneTree(root)
    ans.printTree()
    #[1, 1, 1]