Leetcode brush questions diary sword finger offer II 047. Binary tree pruning

Original link （https://leetcode.cn/problems/pOCWxh/）

Title Description

Given a binary tree The root node root , The value of each node of the tree is either 0, Or 1. Please cut off all nodes in the binary tree. The value is 0 The subtree of . node node The subtree of is node In itself , And all node The offspring of .

Example 1

Example 2

Example 3

Data restrictions

• The number of nodes of the binary tree ranges from [1,200]
• The value of a binary tree node can only be 0 or 1

Ideas

For leaf nodes, as long as they are 0 Then the node should be deleted. After all, the leaf node has no child nodes , After deletion, if it has no sibling node, its parent node is the leaf node , Then we have to judge whether its value is 0, If 0 Then you need to delete this node , If its parent node will repeat the mistakes, it needs to continue to delete . From this process, it is not difficult to see , The focus of this problem is the deletion of leaf nodes and the replacement of parent nodes . So we can use recursive method , Start processing from the leaf node , And its parent node is processed synchronously during backtracking . Finally, get the final processed binary tree .
Such as Example 2 The process should be

Code

public TreeNode pruneTree(TreeNode root) {
    
        if(root==null)
			return null;
		root.left=pruneTree(root.left);
		root.right=pruneTree(root.right);
		if(root.val==0&&root.left==null&&root.right==null) {
    
			return null;
		}
		return root;
    }