leetcode
May 14, 2024

Viiisit [LeetCode] - 1325. Delete Leaves With a Given Value

#php#javascript#ruby

keep learning, keep coding!

Problem - Delete Leaves With a Given Value

Given a binary tree root and an integer target, delete all the leaf nodes with value target.

Note that once you delete a leaf node with value target, if its parent node becomes a leaf node and has the value target, it should also be deleted (you need to continue doing that until you cannot).

翻譯蒟蒻

從二元樹中刪除所有值為目標值的葉節點，並且如果他們的父節點因此變成了值為目標值的葉節點也要刪除。

1
2
3
4
Input: root = [1,2,3,2,null,2,4], target = 2
Output: [1,null,3,null,4]
Explanation: Leaf nodes in green with value (target = 2) are removed (Picture in left). 
After removing, new nodes become leaf nodes with value (target = 2) (Picture in center).
1
2
Input: root = [1,3,3,3,2], target = 3
Output: [1,3,null,null,2]
1
2
3
Input: root = [1,2,null,2,null,2], target = 2
Output: [1]
Explanation: Leaf nodes in green with value (target = 2) are removed at each step.

使用遞迴（這題使用後序遍歷）和樹的遍歷方法。所謂的後序遍歷（左-右-根）是在處理父節點之前先處理所有的子節點。這樣的方式確保不會錯過刪除子節點而變成的新葉節點，能夠正確進行連續刪除操作。

Solution - JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} target
 * @return {TreeNode}
 */
var removeLeafNodes = function(root, target) {
    if (!root) return null

    root.left = removeLeafNodes(root.left, target)
    root.right = removeLeafNodes(root.right, target)

    if (!root.left && !root.right && root.val === target) return null

    return root
};

line 20 : 檢查當前節點是否為葉節點（即沒有左子節點和右子節點），並且是否等於目標值。如果兩者都成立，則返回 null 刪除此節點。

Solution - Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {TreeNode} root
# @param {Integer} target
# @return {TreeNode}
def remove_leaf_nodes(root, target)
  if root.nil?
    return nil
  end

  root.left = remove_leaf_nodes(root.left, target)
  root.right = remove_leaf_nodes(root.right, target)

  if root.left.nil? && root.right.nil? && root.val == target
    return nil
  end

  return root
end

Solution - PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function removeLeafNodes($root, $target) {
    if ($root == null) {
        return null;
    }

    $root->left = $this->removeLeafNodes($root->left, $target);
    $root->right = $this->removeLeafNodes($root->right, $target);

    if ($root->left == null && $root->right == null && $root->val == $target) {
      return null;
    }
    
    return $root;
}

LeetCode 傳送門 - Delete Leaves With a Given Value