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

猿大侠 · 公众号 · · 2024-09-28 12:08

正文

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

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

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

来看下今天的算法题，这题是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;// 否则不要删除，直接返回
}