0814._Binary_Tree_Pruning.md

814. Binary Tree Pruning

难度: Medium

刷题内容

原题连接

• https://leetcode-cn.com/problems/binary-tree-pruning/

内容描述

给定二叉树根结点 root ，此外树的每个结点的值要么是 0，要么是 1。

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

( 节点 X 的子树为 X 本身，以及所有 X 的后代。)

示例1:
输入: [1,null,0,0,1]
输出: [1,null,0,null,1]

解题方案

思路 1

遍历二叉树，切除左右子树中无1的子树。

bool dfs(TreeNode* root){
    if(root==NULL)
        return false;
    bool left = dfs(root->left);
    bool right = dfs(root->right);
    if(left==false)
        root->left=NULL;
    if(right==false)
        root->right=NULL;
    return root->val==1||left||right;
}
TreeNode* pruneTree(TreeNode* root) {
    dfs(root);
    return root;
}