0
\$\begingroup\$

https://leetcode.com/problems/delete-nodes-and-return-forest/

Given the root of a binary tree, each node in the tree has a distinct value.

After deleting all nodes with a value in to_delete, we are left with a forest (a disjoint union of trees).

Return the roots of the trees in the remaining forest. You may return the result in any order.

enter image description here

Input: root = [1,2,3,4,5,6,7], to_delete = [3,5] Output: [[1,2,null,4],[6],[7]]

Constraints:

The number of nodes in the given tree is at most 1000. Each node has a distinct value between 1 and 1000. to_delete.length <= 1000 to_delete contains distinct values between 1 and 1000.

Please review for performance and style.

using System.Collections.Generic;
using System.Linq;
using GraphsQuestions;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace TreeQuestions
{
    /// <summary>
    /// https://leetcode.com/problems/delete-nodes-and-return-forest/
    /// </summary>
    [TestClass]
    public class DeleteNodesAndReturnForestTest
    {
        [TestMethod]
        public void ExampleTest()
        {
            var root = new TreeNode(1);
            root.left = new TreeNode(2);
            root.left.left = new TreeNode(4);
            root.left.right = new TreeNode(5);
            root.right = new TreeNode(3);
            root.right.left = new TreeNode(6);
            root.right.right=new TreeNode(7);
            var deleteNodes=new DeleteNodesAndReturnForest();
            var res = deleteNodes.DelNodes(root, new[] {3, 5});
            Assert.AreEqual(6,res[0].val);
            Assert.AreEqual(7,res[1].val);
            Assert.AreEqual(1,res[2].val);
            Assert.AreEqual(2,res[2].left.val);
            Assert.AreEqual(4,res[2].left.left.val);
            Assert.IsNull(res[2].left.right);

        }
    }

    public class DeleteNodesAndReturnForest
    {
        List<TreeNode> _forest;
        public IList<TreeNode> DelNodes(TreeNode root, int[] to_delete)
        {
            if (root == null || to_delete == null || to_delete.Length == 0)
            {
                return _forest;
            }
            _forest = new List<TreeNode>();
            Helper(root, to_delete);
            if (!to_delete.Contains(root.val))
            {
                _forest.Add(root);
            }
            return _forest;
        }

        private TreeNode Helper(TreeNode root, int[] to_delete)
        {
            if (root == null)
            {
                return null;
            }
            //first do the recursion
            root.left = Helper(root.left, to_delete);
            root.right = Helper(root.right, to_delete);
            //when coming back from recursion(post-order). all the subtrees is already deleted
            //delete root and add to the forest the left and right leaves
            if (to_delete.Contains(root.val))
            {
                if (root.left != null)
                {
                    _forest.Add(root.left);
                }
                if (root.right != null)
                {
                    _forest.Add(root.right);
                }

                return null;
            }

            return root;
        }
    }
}
\$\endgroup\$
2
  • \$\begingroup\$ Just wondering: does gili convey any meaning? \$\endgroup\$
    – vnp
    Apr 11 '20 at 21:08
  • \$\begingroup\$ @vnp LOL my name is Gilad just a nick name for temp variable. I forgot to replace. \$\endgroup\$
    – Gilad
    Apr 11 '20 at 21:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.