Problem:
题目大意:把不含有1的节点的子树全部删除。
https://leetcode.com/problems/binary-tree-pruning/description/
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,0,0,1] Output: [1,null,0,null,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,0,1,0,0,0,1] Output: [1,null,1,null,1]
Example 3: Input: [1,1,0,1,1,0,1,0] Output: [1,1,0,1,1,null,1]
Note:
- The binary tree will have at most
100 nodes
. - The value of each node will only be
0
or1
.
Solution: Recursion
Time complexity: O(n)
Space complexity: O(h)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua // Running time: 6 ms class Solution { public: TreeNode* pruneTree(TreeNode* root) { if (!root) return root; root->left = pruneTree(root->left); root->right = pruneTree(root->right); if (root->val == 1 || root->left || root->right) return root; delete root; return nullptr; } }; |
Java
1 2 3 4 5 6 7 8 9 10 |
// Author: Huahua // Running time: 2 ms class Solution { public TreeNode pruneTree(TreeNode root) { if (root == null) return root; root.left = pruneTree(root.left); root.right = pruneTree(root.right); return (root.val == 1 || root.left != null || root.right != null) ? root : null; } } |
Python3
1 2 3 4 5 6 7 8 |
// Author: Huahua // Running time: 36 ms class Solution: def pruneTree(self, root): if not root: return root root.left = self.pruneTree(root.left) root.right = self.pruneTree(root.right) return root if root.val == 1 or root.left or root.right else None |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment