LeetCode814 二叉树剪枝

剪枝：Pruning, as the name suggests, is the pruning of a tree,In reality, the purpose of pruning a tree is to make it look better,The same is true for operations on binary trees in programs,called in the program“好看”That is, the time complexity of the algorithm can be reduced.Pruning is like a decision tree,It is useful in areas such as machine learning overfitting,But I don't understand the use of pruning in real scenarios,It's just a matter of understanding from the point of view of the question（害）.

题目描述

Given a binary tree root noderoot,此外树的每个结点的值要么是 0,要么是 1.

Return to remove all not included1的子树的原二叉树

节点x的子树包含节点xitself and allx的后代

说明：

给定的二叉树最多有100个节点

每个节点的值只会为0或1

示例

1. 输入：[1,null,0,0,1]

   输出：[1,null,0,null,1]

   图示：

说明：

Only the red one0满足“All subtree nodes are not included1”,另外一个0Its right subtree obviously has one1,所以不用删除,Note that the stipulations given in the title are：节点x的子树包含节点xitself and allx的后代

2. 输入：[1,0,1,0,0,0,1]

   输出：[1,null,1,null,1]

3. 输入：[1,1,0,1,1,0,1,0]

   输出：[1,1,0,1,1,null,1]

   图示：

题目解析

  由上面的示例可以看出,The value of each removed node is 0,And its left and right subtrees are both “空”,即是“叶子节点”.拿示例2来看,If we delete it recursively,The recursive stack first operates on the last node pushed onto the stack,即The recursive way is bottom-up进行操作的.This is when the example is formally processed2the second node in 0(从左往右算)时,Two of its left and right subtrees0have all been deleted,So this node can also be deleted,Repeat this process to delete all nodes that meet the conditions.The code for the recursive implementation is concise,代码如下：

class Solution {
    
    public TreeNode pruneTree(TreeNode root) {
    
        if (root == null) {
    
            return null;
        }
        root.left = pruneTree(root.left);	// Get the new subtree after pruning the left subtree
        root.right = pruneTree(root.right);	//Get the new subtree after pruning the right subtree
        if (root.left == null && root.right == null && root.val == 0) {
    	//The left and right subtrees are empty and have values0,要删除,返回null即可
            return null;
        }
        return root;
    }
}

程序运行结果：

注：虽然形式很简单,But the key is to understand the recursive operation process.

For more solutions, see the original question：814.二叉树剪枝