[LeetCode] Binary Tree Pruning

Problem: Given the root of a binary tree, return the same tree where every subtree (of the given tree) not containing a 1 has been removed.

A subtree of a node node is node plus every node that is a descendant of node.

Example:

Input: root = [1,null,0,0,1]
Output: [1,null,0,null,1]
Explanation: 
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.

Input: root = [1,0,1,0,0,0,1]
Output: [1,null,1,null,1]

Input: root = [1,1,0,1,1,0,1,0]
Output: [1,1,0,1,1,null,1]

Approach: We can simply do a post order traversal here to solve this problem. Just look at the implementation to understand the approach.

Implementation in C#:

    public TreeNode PruneTree(TreeNode root) 

    {

        if (root == null)

        {

            return null;

        }        

        root.left = this.PruneTree(root.left);

        root.right = this.PruneTree(root.right);

        return root.left == null && root.right == null && root.val == 0 ? null : root;

    }

Complexity: O(n)