【力扣814】二叉树剪枝

814 二叉树剪枝

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

源代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    //  移除所有不包含1的子树
    TreeNode* pruneTree(TreeNode* root) {
        if(!root){
            return nullptr;
        }
        TreeNode* a = pruneTree(root->left);
        TreeNode* b = pruneTree(root->right);
        if(!a){
            root->left = nullptr;
        }
        if(!b){
            root->right = nullptr;
        }
        if(!root->left && !root->right && root->val!=1){
            return nullptr;
        }
        return root;
    }
};

类似之前一道左右子树各给父节点返回一个标志的解法。

注意节点的val是0或1的区别：在左右子树都不包含1的情况下，若父节点不为1，则一起删除，否则保留父节点。

左右孩子各给父节点返回一个标志，表示是否含有1；

父节点同样给自己的父节点返回一个类似的标志，这个操作对所有节点都是一样的；

父节点收到左右孩子的标志以后，若某个孩子所在的子树不含1，则将这一路设置为nullptr，再检查自己的val是否为1，若不为1，则给自己的父节点返回不含1的标志，否则告诉自己的父节点自己有1，此时这个节点的左右孩子中不含1的子树已经设置为nullptr，达到了一种传递的效果。

如果使用val作为标志位：

左右子树都为0，自己为0，返回nullptr √

左右子树有1，自己为0，执行左右孩子时走return root，该分支被误判位nullptr ❌

实际上只有都为0的情况会返回nullptr，应该彻底删除，其他情况都应该保留。

修改执行左右分支后对结果的判断条件，删除root->val!=1的判定

修改为：

补充：
图解