Solving 450 LeetCode Problems

I'm a big believer that you should do what you like to do, what you're passionate about. 

One of my hobbies is LeetCode. I say as a hobby because that's what it really is: there is no expectation from my part that these problems will help me professionally (if one day they do, that's a bonus). I truly just do it because I enjoy - just as if you like playing video games, you should then just play. Just be happy :) 

Today I got to my 450th solved problem (over a couple of years now). The problem was to "find the leaves on a binary tree, and keep removing them and finding new leaves": https://leetcode.com/submissions/detail/271722558/

The solution is to literally just do that: find the leaves (DFS), remove them (that's why you need to pass the parent node along), and repeat until all the nodes are gone. On average the execution time will actually be NLogN since at every point you remove 1/2 the tree but you still need to traverse all nodes, hence NLogN. Code is below, cheers, ACC.


public class Solution
{
    public IList<IList<int>> FindLeaves(TreeNode root)
    {
        List<IList<int>> retVal = new List<IList<int>>();
        while (root != null)
        {
            List<int> list = new List<int>();
            TreeNode parent = null;
            FindLeavesAndDelete(ref parent, true, ref root, list);
            retVal.Add(list);
        }

        return retVal;
    }

    private void FindLeavesAndDelete(ref TreeNode parentNode,
                                        bool isRightNode,
                                        ref TreeNode node,
                                        IList<int> list)
    {
        if (node == null) return;
        if (node.left == null && node.right == null)
        {
            list.Add(node.val);
            if (parentNode != null)
            {
                if (isRightNode)
                {
                    parentNode.right = null;
                }
                else
                {
                    parentNode.left = null;
                }
            }
            else
            {
                node = null;
            }
            return;
        }
        if (node.left != null)
        {
            FindLeavesAndDelete(ref node,
                                false,
                                ref node.left,
                                list);
        }
        if(node.right != null)
        {
            FindLeavesAndDelete(ref node,
                                true,
                                ref node.right,
                                list);
        }
    }
}

Comments

Popular posts from this blog

Count Binary Substrings

Count Vowels Permutation: Standard DP

Maximum Number of Balloons