Force deduction solution summary 814 binary tree pruning

  Directory links ：

Force buckle programming problem - The solution sums up _ Share + Record -CSDN Blog

GitHub Synchronous question brushing items ：

https://github.com/September26/java-algorithms

Original link ： Power button

describe ：

Give you the root node of the binary tree  root , In addition, the value of each node of the tree is either 0 , Or 1 .

Return to remove all excluded 1 The original binary tree of the subtree .

node node The subtree of is node Plus all itself node The offspring of .

Example 1：

Input ：root = [1,null,0,0,1]
Output ：[1,null,0,null,1]
explain ：
Only the red nodes meet the conditions “ All do not contain 1 The subtree of ”. On the right is the answer .
Example 2：

Input ：root = [1,0,1,0,0,0,1]
Output ：[1,null,1,null,1]
Example 3：

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

Tips ：

The number of nodes in the tree is in the range [1, 200] Inside
Node.val by 0 or 1

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/binary-tree-pruning
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking ：

*  Their thinking ：
*  The idea of recursion ,
*  Every time you recurse , Judge separately left,right, It does not contain 1, If none , Then return to false. Instead, return to true.
*  The upper layer receives false when , Delete this node .

Code ：

public class Solution814 {

    public TreeNode pruneTree(TreeNode root) {
        boolean b = have1Node(root);
        return !b ? null : root;
    }

    /**
     * root Contained in the 1 Then return to true, Otherwise false
     *
     * @param root
     * @return
     */
    public boolean have1Node(TreeNode root) {
        TreeNode left = root.left;
        TreeNode right = root.right;
        boolean result = false;
        if (left != null) {
            if (have1Node(left)) {
                result = true;
            } else {
                root.left = null;
            }
        }
        if (right != null) {
            if (have1Node(right)) {
                result = true;
            } else {
                root.right = null;
            }
        }
        return result || root.val == 1;
    }
}