题解35 | 子不教父之过#修剪叶子#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return TreeNode类
     */
    TreeNode* pruneLeaves(TreeNode* root) {
        // write code here
        if(root == NULL) 
            return NULL;
        else if (root->left != NULL 
                && root->left->left == NULL 
                && root->left->right == NULL)
            return nullptr;
        else if (root->right != NULL 
                && root->right->left == NULL 
                && root->right->right == NULL)
            return nullptr;
        //子不教，父之过。叶坏不剪叶，害除要断枝
        root->left = pruneLeaves(root->left);
        root->right = pruneLeaves(root->right);

        return root;
    }
};

算法的基本思想

递归地遍历二叉树，对于每个节点，判断其左右子树是否为叶子节点（即左右子树为空），

如果是，则将该子树剪掉（即置为nullptr），然后继续递归地处理其左右子树。

时间复杂度

算法的时间复杂度为O(n)，其中n为二叉树的节点个数，因为需要遍历所有的节点。

空间复杂度

空间复杂度为O(h)，其中h为二叉树的高度，因为递归调用的栈空间取决于递归的深度。