[leetcode题解]1325.Delete Leaves With a Given Value(删除给定值的叶子节点)

给你一棵以 root 为根节点的的二差树和一任意一个value值 ,需要删除树种所有与该值相等的叶子节点 。

caution,一旦去除值为value的叶子节点,其上一个节点点就可能变成新的叶子节点。需要对新的叶子节点做同样的判断处理,即如果值相同,需要重复该操作,一直做到不能删除为止。

题解:

本题目是一个有关树的操作,题目的意思是给定一个二叉树,并给定一个数字,要求在二叉树中搜索所有的叶子,如果其值等于给定的值,则要将这个叶子从二叉树中删除。

要注意:当一个节点他的所有子树都被删除后,他自己就变成了一个新的叶子节点,也要进行判断。

比如一个节点为1他的左子节点为1,右子节点也为1,如果给定的数为1的话,先要将这个节点的左右两个子叶子节点都删除掉,此时当前节点就变成了一棵叶子节点,此时判断当前节点也为1,也是要删除的。

看到这个题目,从题目中就能看出用递归的方法非常简单,对任意一个节点先处理其左节点,然后再处理其右节点。并把处理后的子树返回。

这样如果左子树全被删掉,就返回NULL,同理如果右子树也全被删掉,则也返回NULL,然后在进行当前节点的处理,一判断其左右子树为NULL,则可以得出当前节点现在为叶子节点。

根据如上分析,很容易写出递归处理的代码。

代码如下:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* removeLeafNodes(TreeNode* root, int target) {
        return remove(root, target);
    }
private:
    TreeNode *remove(TreeNode *root, int target) {
        if (root == NULL) {
            return NULL;
        }
        
        if (root->left != NULL) {
            root->left = remove(root->left, target);
        }
        
        if (root->right != NULL) {
            root->right = remove(root->right, target);
        }
        
        if (root->left == NULL &&
            root->right == NULL &&
            root->val == target) {
            return NULL;
        }
        return root;
    }
};

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]1325.Delete Leaves With a Given Value(删除给定值的叶子节点)

本文链接地址:https://www.iaccepted.net/algorithm/leetcode/229.html

相关文章