二叉树剪枝

原题：

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

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

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

  1. 示例1:
  2. 输入: [1,null,0,0,1]
  3. 输出: [1,null,0,null,1]
  5. 解释: 
  6. 只有红色节点满足条件“所有不包含 1 的子树”。
  7. 右图为返回的答案。
示例2:
输入: [1,0,1,0,0,0,1]
输出: [1,null,1,null,1]

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

说明:

  • 给定的二叉树最多有 100 个节点。
  • 每个节点的值只会为 0 或 1 。

解法一：

解题方法：

class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        if(!root) return root;
        if(NoOne(root)) return nullptr;   //有可能整棵树都没1
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty())
        {
            TreeNode* node=que.front();
            que.pop();
            if(NoOne(node->left)) node->left=nullptr;
            if(NoOne(node->right)) node->right=nullptr;
            if(node->left) que.push(node->left);
            if(node->right) que.push(node->right);
        }
        return root;
    }

    bool NoOne(TreeNode* root)
    {
        if(!root) return true;
        return (root->val!=1)&&NoOne(root->left)&&NoOne(root->right);
    }
};

解法二（优化递归）：

class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        if(!root) return root;
        if(NoOne(root)) return nullptr;   //有可能整棵树都没1
        return root;
    }

    bool NoOne(TreeNode* root)
    {
        if(!root) return true;
        if(NoOne(root->left)) root->left=nullptr;
        if(NoOne(root->right)) root->right=nullptr;
        return (root->val!=1)&&NoOne(root->left)&&NoOne(root->right);
    }
};

做题小结：

针对解法一：

  1. 非常朴实无华的思路，遍历树上每个节点，对每个结点检查是否为全0树，检查是否为全0树，则又靠遍历该子树的方式。

针对解法二：

  1. 在一的基础之上，将代码更加简化了，直接在子函数中就完成了剪枝

  2. 但是很奇怪，为什么花的时间反而更长了？？？
    听说这个执行时间本身就是动态的，提交代码给服务器，服务器执行后返回时间，这个时间和代码本身、服务器当时的硬件、软件状态等因素都会有关系，而且时间单位是ms。