{"id":6117,"date":"2020-01-20T18:24:54","date_gmt":"2020-01-21T02:24:54","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6117"},"modified":"2020-01-20T18:25:33","modified_gmt":"2020-01-21T02:25:33","slug":"leetcode-1325-delete-leaves-with-a-given-value","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-1325-delete-leaves-with-a-given-value\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1325. Delete Leaves With a Given Value"},"content":{"rendered":"\n<p>Given a binary tree&nbsp;<code>root<\/code>&nbsp;and an integer&nbsp;<code>target<\/code>, delete all the&nbsp;<strong>leaf nodes<\/strong>&nbsp;with value&nbsp;<code>target<\/code>.<\/p>\n\n\n\n<p>Note&nbsp;that once you delete a leaf node with value&nbsp;<code>target<\/code><strong>,&nbsp;<\/strong>if it&#8217;s parent node becomes a leaf node and has the value&nbsp;<code>target<\/code>, it should also be deleted (you need to continue doing that until you can&#8217;t).<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/01\/09\/sample_1_1684.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> root = [1,2,3,2,null,2,4], target = 2\n<strong>Output:<\/strong> [1,null,3,null,4]\n<strong>Explanation:<\/strong> Leaf nodes in green with value (target = 2) are removed (Picture in left). \nAfter removing, new nodes become leaf nodes with value (target = 2) (Picture in center).\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/01\/09\/sample_2_1684.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> root = [1,3,3,3,2], target = 3\n<strong>Output:<\/strong> [1,3,null,null,2]\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/01\/15\/sample_3_1684.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> root = [1,2,null,2,null,2], target = 2\n<strong>Output:<\/strong> [1]\n<strong>Explanation:<\/strong> Leaf nodes in green with value (target = 2) are removed at each step.\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> root = [1,1,1], target = 1\n<strong>Output:<\/strong> []\n<\/pre>\n\n\n\n<p><strong>Example 5:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> root = [1,2,3], target = 1\n<strong>Output:<\/strong> [1,2,3]\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= target&nbsp;&lt;= 1000<\/code><\/li><li>Each tree has at most&nbsp;<code>3000<\/code>&nbsp;nodes.<\/li><li>Each node&#8217;s value is between&nbsp;<code>[1, 1000]<\/code>.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Recursion<\/strong><\/h2>\n\n\n\n<p>Post-order traversal<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\/\/ Author: Huahua\nclass Solution {\npublic:\n  TreeNode* removeLeafNodes(TreeNode* root, int target) {\n    if (!root) return nullptr;        \n    root->left = removeLeafNodes(root->left, target);        \n    root->right = removeLeafNodes(root->right, target);  \n    return root->left || root->right || root->val != target \n      ? root : nullptr;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given a binary tree&nbsp;root&nbsp;and an integer&nbsp;target, delete all the&nbsp;leaf nodes&nbsp;with value&nbsp;target. Note&nbsp;that once you delete a leaf node with value&nbsp;target,&nbsp;if it&#8217;s parent node becomes a&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[45],"tags":[177,376,17,28],"class_list":["post-6117","post","type-post","status-publish","format-standard","hentry","category-tree","tag-medium","tag-on","tag-recursion","tag-tree","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6117","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=6117"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6117\/revisions"}],"predecessor-version":[{"id":6119,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6117\/revisions\/6119"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6117"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6117"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6117"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}