程序员,迟早要被自己人卷死。。。

Python客栈

共 5148字,需浏览 11分钟

 ·

2024-08-03 17:00


Python客栈设为“星标
第一时间收到最新资讯


最近网上一程序员找工作,还没参加面试就开始卷了,前端,后端,运维,产品,测试,它一个人全干。就算是生产队的驴也没这样干的,关键这还是它自己要求的。网友评论到:这人一跑,公司直接倒闭。

网友评论:



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


来看下今天的算法题,这题是LeetCode的第563题:二叉树的坡度。


问题描述



来源:LeetCode第563题
难度:简单

给你一个二叉树的根节点 root ,计算并返回整个树的坡度 。一个树的节点的坡度定义即为,该节点左子树的节点之和和右子树节点之和的差的绝对值。如果没有左子树的话,左子树的节点之和为 0 ;没有右子树的话也是一样。空结点的坡度是 0 。


整个树的坡度就是其所有节点的坡度之和。


示例1:

输入:root = [1,2,3]

输出:1

解释

节点 2 的坡度:|0-0| = 0(没有子节点)

节点 3 的坡度:|0-0| = 0(没有子节点)

节点 1 的坡度:|2-3| = 1(左子树就是左子节点,所以和是 2 ;右子树就是右子节点,所以和是 3 )

坡度总和:0 + 0 + 1 = 1

示例2:

输入:root = [4,2,9,3,5,null,7]

输出:15

解释

节点 3 的坡度:|0-0| = 0(没有子节点)

节点 5 的坡度:|0-0| = 0(没有子节点)

节点 7 的坡度:|0-0| = 0(没有子节点)

节点 2 的坡度:|3-5| = 2(左子树就是左子节点,所以和是 3 ;右子树就是右子节点,所以和是 5 )

节点 9 的坡度:|0-7| = 7(没有左子树,所以和是 0 ;右子树正好是右子节点,所以和是 7 )

节点 4 的坡度:|(3+5+2)-(9+7)| = |10-16| = 6(左子树值为 3、5 和 2 ,和是 10 ;右子树值为 9 和 7 ,和是 16 )

坡度总和:0 + 0 + 0 + 2 + 7 + 6 = 15


  • 树中节点数目的范围在 [0, 10^4] 内

  • -1000 <= Node.val <= 1000


问题分析



这题让累加二叉树中所有子树的左右子树的差值,有点绕,我们举个例子,比如示例 2 中,节点 3 的左右子树都为空,它们的差值是 0 。节点 2 的左右子树的差值是 2(5-3),节点 9 的左右子树的差值是 7(7-0),节点 4 的左右子树差值是 6(16-10),累加起来就是2+7+6=15。

所以这题是自底往上累加子树所有节点之和,可以参考二叉树的后序遍历。

JAVA:
int ans = 0;

public int findTilt(TreeNode root) {
    dfs(root);
    return ans;
}

// 计算当前子树和
private int dfs(TreeNode root) {
    if (root == null)
        return 0;
    int left = dfs(root.left);// 左子树的所有节点之和
    int right = dfs(root.right);// 右子树的所有节点之和
    ans += Math.abs(left - right);// 累加它们的差值
    return left + right + root.val;
}

C++:
public:
    int ans = 0;

    int findTilt(TreeNode *root) {
        dfs(root);
        return ans;
    }

    // 计算当前子树和
    int dfs(TreeNode *root) {
        if (root == nullptr)
            return 0;
        int left = dfs(root->left);// 左子树的所有节点之和
        int right = dfs(root->right);// 右子树的所有节点之和
        ans += abs(left - right);// 累加它们的差值
        return left + right + root->val;
    }

Python:
def findTilt(self, root: Optional[TreeNode]) -> int:
    ans = 0

    # 计算当前子树和
    def dfs(node):
        if node is None:
            return 0
        left = dfs(node.left)  # 左子树的所有节点之和
        right = dfs(node.right)  # 右子树的所有节点之和
        nonlocal ans
        ans += abs(left - right)  # 累加它们的差值
        return left + right + node.val

    dfs(root)
    return ans


往期回顾

1、12个Python循环中的性能监控与优化工具和技巧
2、一个 Bug 改了三次,汗流浃背了。。
3、Linux Mint 22“Wilma”正式发布
4、不到2MB,很炸裂的神器!
5、8年前就免费的功能还在扣费!运营商的回应令人无语
      


点击关注公众号,阅读更多精彩内容

浏览 97
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报