LeetCode 814. Binary Tree Pruning

发布时间：2020-12-14 04:43:12 所属栏目：大数据来源：网络整理

导读：原题链接在这里：https://leetcode.com/problems/binary-tree-pruning/ 题目： We are given the head node? root ?of a binary tree,where additionally every node‘s value is either a 0 or a 1. Return the same tree where every subtree (of the give

原题链接在这里：https://leetcode.com/problems/binary-tree-pruning/

题目：

We are given the head node?root?of a binary tree,where additionally every node‘s value is either a 0 or a 1.

Return the same tree where every subtree (of the given tree) not containing a 1 has been removed.

(Recall that the subtree of a node X is X,plus every node that is a descendant of X.)

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

Example 2:
Input: [1,1,1]

Example 3:
Input: [1,0]
Output: [1,1]

Note:

The binary tree?will?have?at?most?100 nodes.
The value of each node will only be?0?or?1.

题解：

Check left subtree is all zero,if yes,left child is null.

Check right subtree is all zero,right child is null.

If both left subtree and right subtree are all zero,and cur node‘s val is 0,then return true,which means current subtree is all zero.

Check back to root node,if all zero,then root is deleted.

Time Complexity: O(n).

Space: O(h).

AC Java:

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 class Solution {
11     public TreeNode pruneTree(TreeNode root) {
12         if(root == null){
13             return null;
14         }
15         
16         boolean rootAllZero = isAllZero(root);
17         if(rootAllZero){
18             return null;
19         }
20         
21         return root;
22     }
23     
24     
25     private boolean isAllZero(TreeNode root){
26         if(root == null){
27             return true;
28         }
29         
30         boolean left = isAllZero(root.left);
31         boolean right = isAllZero(root.right);
32         if(left){
33             root.left = null;
34         }
35         
36         if(right){
37             root.right = null;
38         }
39         
40         if(left && right && root.val==0){
41             return true;
42         }
43         
44         return false;
45     }
46 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!