当前位置：网站首页>[binary tree] delete points to form a forest

[binary tree] delete points to form a forest

2022-07-07 12:47:00 【How cold it is】

0x00 subject

Give the root node of the binary tree root
Each node in the tree has a different value
If the node value is to_delete It appears that
Let's take this node from the tree delete
Finally get a forest （ A collection of disjoint trees ）

Return to every tree in the forest
You can organize the answers in any order

0x01 Ideas

A node needs Delete when
It needs to be judged about Whether the node is empty
If it is not empty add to To the result array
And then return a Blank nodes (nil) To the top
The upper layer can be directly replaced
therefore , So this is the way to think about it
Use In the following order Traversal mode is ok

0x02 solution

Language ：Swift

Tree node ：TreeNode

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}

solution ：

func delNodes(_ root: TreeNode?, _ to_delete: [Int]) -> [TreeNode?] {
    var res: [TreeNode?] = []
    
    func del(_ root: TreeNode?, _ to_delete: [Int]) -> TreeNode? {
        guard let root = root else { return nil }
        
        //  Delete the left and right subtrees respectively 
        let left = del(root.left, to_delete)
        let right = del(root.right, to_delete)
        
        //  Update the left and right subtrees 
        root.left = left
        root.right = right
        
        //  Nodes need to be deleted 
        if to_delete.contains(root.val) {
            if left != nil {
                res.append(left)
            }
            if right != nil {
                res.append(right)
            }
            return nil
        }
        
        return root
    }
    
    //  Whether the root node needs to be deleted ？
    let r = del(root, to_delete)
    if r != nil {
        res.append(r)
    }
    
    return res
}