京东素质面没过，离谱到家了。。

专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

一网友在京东面试，测评，笔试，小组面，专业面，都过了，一路畅通无阻，结果在素质面的时候给挂了，网友评论道：离谱他妈给离谱开门，真是离谱到家了。还有的网友说：京东没素质，有素质的人他不要。

我很好奇素质面是怎么面的，通过回答问题就能判断一个人有没有素质吗？前面几轮都过了，说明专业性没问题，还搞个素质面，真的是多余，关键还给人家挂了。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第814题：二叉树剪枝。

问题描述

来源：LeetCode第814题

难度：中等

给你二叉树的根结点 root ，此外树的每个结点的值要么是 0 ，要么是 1 。返回移除了所有不包含 1 的子树的原二叉树。节点 node 的子树为 node 本身加上所有 node 的后代。

示例1：

输入：root = [1,null,0,0,1] 输出：[1,null,0,null,1] 解释： 只有红色节点满足条件“所有不包含 1 的子树”。右图为返回的答案。

示例2：

输入：root = [1,0,1,0,0,0,1] 输出：[1,null,1,null,1]

• 树中节点的数目在范围 [1, 200] 内

• Node.val 为 0 或 1

问题分析

这题说的是如果一颗子树所有节点值都是 0 ，就把这棵子树给删除。如果子树中只要有一个节点为 1 ，这棵子树就不能删除。

我们可以从下往上遍历二叉树，因为最下层的就是叶子节点，如果它是 0 ，把它删除就行了。 从下往上遍历的时候，有的节点不是叶子节点，有可能子节点被删除之后，它就变成了叶子节点 。

所以这里我们只需要对叶子节点操作即可，二叉树从下往上遍历可以使用后序遍历的方式，代码比较简单，我们来看下。

JAVA：

// 从下往上操作二叉树，参考二叉树的后序遍历
public TreeNode pruneTree(TreeNode root) {
    if (root == null)
        return null;
    // 当前节点可能不是叶子节点，但如果他的子节点
    // 都删除完了，它就变成了叶子节点。
    root.left = pruneTree(root.left);// 剪枝左子树
    root.right = pruneTree(root.right);// 剪枝右子树
    // 如果叶子节点的值是0，就把他给删除，返回一个空的节点
    if (root.left == null && root.right == null && root.val == 0)
        return null;
    return root;// 否则不要删除，直接返回
}

C++：

// 从下往上操作二叉树，参考二叉树的后序遍历
public:
    TreeNode *pruneTree(TreeNode *root) {
        if (!root)
            return nullptr;
        // 当前节点可能不是叶子节点，但如果他的子节点
        // 都删除完了，它就变成了叶子节点。
        root->left = pruneTree(root->left);// 剪枝左子树
        root->right = pruneTree(root->right);// 剪枝右子树
        // 如果叶子节点的值是0，就把他给删除，返回一个空的节点
        if (!root->left && !root->right && !root->val)
            return nullptr;
        return root;// 否则不要删除，直接返回
    }

Python：

# 从下往上操作二叉树，参考二叉树的后序遍历
def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
    if not root:
        return root
    #  当前节点可能不是叶子节点，但如果他的子节点
    #  都删除完了，它就变成了叶子节点。
    root.left = self.pruneTree(root.left)  # 剪枝左子树
    root.right = self.pruneTree(root.right)  # 剪枝右子树
    #  如果叶子节点的值是0，就把他给删除，返回一个空的节点
    if not root.left and not root.right and root.val == 0:
        return None
    return root  # 否则不要删除，直接返回

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。