C# - recursion, remove leaves as you go (not optimal)


  • 0

    After this attempt I saw the better way to solve this problem which is to count height with leaf being height 0 then use the height as the index of the list the node should be added to. Clearly the other solution is much better.

    public IList<IList<int>> FindLeaves(TreeNode root) 
    {
        IList<IList<int>> lists = new List<IList<int>>();
        IList<int> curr = new List<int>();
        bool rootIsLeaf = root == null;
        while (!rootIsLeaf)
        {
            rootIsLeaf = RemoveLeaves(root, curr);
            lists.Add(curr);
            curr = new List<int>();
        }
        return lists;
    }
    
    public bool RemoveLeaves(TreeNode node, IList<int> curr)
    {
        if (node.left == null && node.right == null)
        {
            curr.Add(node.val);
            
            // return true if node is a leaf, otherwise false
            return true;
        }
        else
        {
            if (node.left != null && RemoveLeaves(node.left, curr))
            {
                node.left = null;
            }
            if (node.right != null && RemoveLeaves(node.right, curr))
            {
                node.right = null;
            }
            return false;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.