Sponsored
Sponsored
This approach uses post-order traversal to traverse each subtree and decide if it should be pruned. Starting from the leaf nodes, it recursively checks if a subtree contains a 1. If a subtree doesn't contain any 1s, it returns null. This way, when the recursion unwinds, only relevant subtrees are kept.
Time Complexity: O(N), where N is the number of nodes, since each node is visited once.
Space Complexity: O(H), where H is the height of the tree, due to the recursive stack space.
1#include <stdlib.h>
2
3struct TreeNode {
4 int val;
5 struct TreeNode* left;
6 struct TreeNode* right;
7};
8
9struct TreeNode* pruneTree(struct TreeNode* root) {
10 if (root == NULL) return NULL;
11
12 root->left = pruneTree(root->left);
13 root->right = pruneTree(root->right);
14
15 if (root->val == 0 && root->left == NULL && root->right == NULL) {
16 free(root);
17 return NULL;
18 }
19 return root;
20}The provided C code represents a function that conducts a post-order traversal starting from the given root node. It uses recursion to visit each node, first addressing the left and right subtrees. If a node's value is 0 and both its subtrees are NULL, the node is pruned by freeing its memory and returning NULL. Otherwise, the node is returned intact. The traversal ensures all subtrees without a 1 are effectively pruned away.
By utilizing an iterative traversal using a stack, the tree can be pruned without recursion. This approach mimics the recursion stack by using an explicit stack to manage nodes that need to be processed. Once the subtree rooted at a node is evaluated, decisions are made to prune or retain nodes based on whether a 1 is found.
Time Complexity: O(N), as we are ensuring every node is visited.
Space Complexity: O(H), attributed to the height of the tree in terms of stack use.
1class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* pruneTree(TreeNode* root) {
std::stack<TreeNode*> s;
if (root) s.push(root);
TreeNode* prev = nullptr;
while (!s.empty()) {
TreeNode* node = s.top();
if (!node->left && !node->right || node->left == prev || node->right == prev) {
if (node->val == 0 && (!node->left || node->left == prev) && (!node->right || node->right == prev)) {
if (prev && prev == node->left) node->left = NULL;
if (prev && prev == node->right) node->right = NULL;
}
prev = node;
s.pop();
} else {
if (node->right) s.push(node->right);
if (node->left) s.push(node->left);
}
}
return root->val == 0 && !root->left && !root->right ? NULL : root;
}This C++ solution simulates post-order traversal using a manual stack. The code navigates from root to leaves while managing nodes in a stack. The helper variable determines whether to prune based on conditions of node value and subtree existence, ensuring coherent tree trimming process.