This is one of those problems where the clean idea matters more than the amount of code. For 814. Binary Tree Pruning, the solution in this repository is mainly a straightforward implementation solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: straightforward implementation.
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are pruneTree.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01/**
02We are given the head node root of a binary tree, where additionally every node's value is either a 0 or a 1.
03
04Return the same tree where every subtree (of the given tree) not containing a 1 has been removed.
05
06(Recall that the subtree of a node X is X, plus every node that is a descendant of X.)
07
08Example 1:
09Input: [1,null,0,0,1]
10Output: [1,null,0,null,1]
11
12Explanation:
13Only the red nodes satisfy the property "every subtree not containing a 1".
14The diagram on the right represents the answer.
15
16
17Example 2:
18Input: [1,0,1,0,0,0,1]
19Output: [1,null,1,null,1]
20
21
22
23Example 3:
24Input: [1,1,0,1,1,0,1,0]
25Output: [1,1,0,1,1,null,1]
26
27
28
29Note:
30
31The binary tree will have at most 100 nodes.
32The value of each node will only be 0 or 1.
33**/
34
35//Your runtime beats 100.00 % of cpp submissions.
36/**
37 * Definition for a binary tree node.
38 * struct TreeNode {
39 * int val;
40 * TreeNode *left;
41 * TreeNode *right;
42 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
43 * };
44 */
45/**
46Wrong Answer
47class Solution {
48public:
49 TreeNode* pruneTree(TreeNode* root) {
50 //use DFS
51 if(root==NULL){ //empty node
52 return NULL;
53 }else if(root->left==NULL && root->right==NULL && root->val==0){ //empty subtree
54 return NULL;
55 }else{
56 root->left = pruneTree(root->left);
57 root->right = pruneTree(root->right);
58 }
59 return root;
60 }
61};
62//the combine step:
63if(root->left==NULL && root->right==NULL && root->val==0){ //empty subtree
64 return NULL;
65should be put after divide step:
66root->left = pruneTree(root->left);
67root->right = pruneTree(root->right);
68!
69**/
70class Solution {
71public:
72 TreeNode* pruneTree(TreeNode* root) {
73 if(root==NULL){ //empty node
74 return NULL;
75 }
76 //use DFS
77 root->left = pruneTree(root->left);
78 root->right = pruneTree(root->right);
79 //divide and conquer
80 if(root->left==NULL && root->right==NULL && root->val==0){ //empty subtree
81 return NULL;
82 }
83 return root;
84 }
85};
86
87/**
88Approach #1: Recursion [Accepted]
89Intuition
90
91Prune children of the tree recursively. The only decisions at each node are whether to prune the left child or the right child.
92
93Algorithm
94
95We'll use a function containsOne(node) that does two things: it tells us whether the subtree at this node contains a 1, and it also prunes all subtrees not containing 1.
96
97If for example, node.left does not contain a one, then we should prune it via node.left = null.
98
99Also, the parent needs to be checked. If for example the tree is a single node 0, the answer is an empty tree.
100
101//Java
102class Solution {
103 public TreeNode pruneTree(TreeNode root) {
104 return containsOne(root) ? root : null;
105 }
106
107 public boolean containsOne(TreeNode node) {
108 if (node == null) return false;
109 boolean a1 = containsOne(node.left);
110 boolean a2 = containsOne(node.right);
111 if (!a1) node.left = null;
112 if (!a2) node.right = null;
113 return node.val == 1 || a1 || a2;
114 }
115}
116
117Complexity Analysis
118
119Time Complexity: O(N), where N is the number of nodes in the tree. We process each node once.
120
121Space Complexity: O(H), where H is the height of the tree. This represents the size of the implicit call stack in our recursion.
122**/Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.