Code & Fun

第35天。

今天的题目是Binary Tree Pruning:

简单题,用先序遍历做就好了,而且不需要使用flagcount等额外的变量来判断是否要删除当前节点。

大概逻辑如下:

先序遍历时,用left = pruneTree(left)的方式去调用,在遍历完子树后,当前节点的子树都是只包含1的树了,我们可以通过判断指针是否为空来确定子树中是否有1,进而判断出是否要删除当前节点,所以我们不需要维护额外的变量来判断。

1
2
3
4
5
6
7
8
TreeNode* pruneTree(TreeNode* root) {
if (root == nullptr) return nullptr;
root->left = pruneTree(root->left);
root->right = pruneTree(root->right);
if (root->left || root->right || root->val == 1) return root;
delete root;
return nullptr;
}

本文首发于Code & Fun