题目地址：https://leetcode.com/problems/binary-tree-pruning/description/
题目描述
Weare 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:
1、 Thebinarytreewillhaveatmost100nodes.；
2、 Thevalueofeachnodewillonlybe0or1.；
题目大意
把一棵树的所有不含1的子树都删除。子树的定义是自身节点和所有子节点。
解题方法
后序遍历
这个题一看还是dfs啊～习惯了新定义一个函数dfs了，但这次不需要了。我们直接把节点的左孩子和右孩子重新设置就好了。这个题是后序遍历！
一定要注意的是，我们判断这个节点是叶子节点并且节点值是1的这个步骤要放在左右子树处理之后。可以从Example2中看出来，如果0节点的左右子节点都是0，那么把左右节点都减去了之后，还要判断自身是不是0，然后把自己也剪了。也就是说这一步相当于后序遍历，把孩子都处理结束之后，然后再处理自身。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def pruneTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if not root: return
root.left = self.pruneTree(root.left)
root.right = self.pruneTree(root.right)
if not root.left and not root.right and root.val == 0:
return None
return root
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
C++版本代码如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* pruneTree(TreeNode* root) {
if (!root) return nullptr;
root->left = pruneTree(root->left);
root->right = pruneTree(root->right);
if (!root->left && !root->right)
return root->val == 1 ? root : nullptr;
return root;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发