題目描述

給出二叉樹的根節(jié)點(diǎn) root，樹上每個(gè)節(jié)點(diǎn)都有一個(gè)不同的值。

如果節(jié)點(diǎn)值在 to_delete 中出現(xiàn)，我們就把該節(jié)點(diǎn)從樹上刪去，最后得到一個(gè)森林（一些不相交的樹構(gòu)成的集合）。

返回森林中的每棵樹。
來源：https://leetcode-cn.com/problems/delete-nodes-and-return-forest

如輸入一棵樹和待刪除集合[3,5]：

返回：[[1,2,null,4],[6],[7]]，即樹因?yàn)楸粍h了3和5兩個(gè)節(jié)點(diǎn)，所以變成了3棵樹，分別是[1,2,null,4]、[6]、[7]

思路

使用深度優(yōu)先遍歷，當(dāng)遇到待刪除節(jié)點(diǎn)時(shí)，如果該節(jié)點(diǎn)有孩子節(jié)點(diǎn)，那么孩子節(jié)點(diǎn)會(huì)獨(dú)立成樹，同時(shí)還需要將該節(jié)點(diǎn)和其父節(jié)點(diǎn)與左右子節(jié)點(diǎn)斷開

實(shí)現(xiàn)

 fun delNodes(root: TreeNode?, to_delete: IntArray): List<TreeNode?> {
        if (root == null) {
            return arrayListOf()
        }
        val forest = arrayListOf(root)
        reverse(root, null, true, to_delete, forest)//根節(jié)點(diǎn)沒有父節(jié)點(diǎn)，所以傳null
        return forest
    }

    //isLeft表示node是parent的左節(jié)點(diǎn)還是右節(jié)點(diǎn)，用于parent需要?jiǎng)h除node時(shí)確定是刪左孩子還是右孩子
    fun reverse(node: TreeNode, parent: TreeNode?, isLeft: Boolean, to_delete: IntArray, forest: ArrayList<TreeNode>) {
        node.left?.let {
            reverse(it, node, true, to_delete, forest)
        }
        node.right?.let {
            reverse(it, node, false, to_delete, forest)
        }
        if (to_delete.contains(node.value)) {//該節(jié)點(diǎn)是待刪除節(jié)點(diǎn)
            node.left?.let { forest.add(it) }//左孩子不為空，則左孩子會(huì)獨(dú)立成樹
            node.right?.let { forest.add(it) }//右孩子同理
            parent?.let { if (isLeft) parent.left = null else parent.right = null }//刪除該節(jié)點(diǎn)和其父節(jié)點(diǎn)的關(guān)聯(lián)
            node.left = null//刪除該節(jié)點(diǎn)和其子節(jié)點(diǎn)的關(guān)聯(lián)
            node.right = null
            forest.remove(node)//考慮刪除根節(jié)點(diǎn)時(shí)，因?yàn)楦?jié)點(diǎn)一開始就在forest中，所以需要把它從forest中刪除
        }
    }