LeetCode C++ 563. Binary Tree Tilt【Tree/DFS】简单
发布日期:2021-07-01 02:52:18
浏览次数:2
分类:技术文章
本文共 1292 字,大约阅读时间需要 4 分钟。
Given a binary tree, return the tilt of the whole tree.
The tilt of a tree node is defined as the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values. Null node has tilt 0
.
The tilt of the whole tree is defined as the sum of all nodes’ tilt.
Example:
Input: 1 / \ 2 3Output: 1Explanation: Tilt of node 2 : 0Tilt of node 3 : 0Tilt of node 1 : |2-3| = 1Tilt of binary tree : 0 + 0 + 1 = 1
Note:
- The sum of node values in any subtree won’t exceed the range of 32-bit integer.
- All the tilt values won’t exceed the range of 32-bit integer.
题意:给定一个二叉树,计算整个树的坡度。
思路 递归后序遍历
注意:一个二叉树的节点坡度定义为,该节点左子树的结点值之和和右子树结点值之和的差的绝对值。空结点的的坡度是 0
。题目要求出整个树的坡度,就是所有节点的坡度之和。递归后序遍历的代码如下:
class Solution { public: int findTilt(TreeNode* root) { int tilt = 0; postorder(root, tilt); return tilt; } int postorder(TreeNode *root, int &tilt) { //返回子树的值之和 if (!root) return 0; if (!root->left && !root->right) return root->val; int lsum = postorder(root->left, tilt); int rsum = postorder(root->right, tilt); tilt += abs(lsum - rsum); return root->val + lsum + rsum; }};
效率较低:
执行用时:32 ms, 在所有 C++ 提交中击败了67.95% 的用户内存消耗:23.2 MB, 在所有 C++ 提交中击败了30.93% 的用户
转载地址:https://memcpy0.blog.csdn.net/article/details/108808504 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
表示我来过!
[***.240.166.169]2024年04月26日 22时55分52秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
今日整理PDF电子书资料
2019-05-02
【语言-c#】C# 超级整数计算
2019-05-02
【商业信息】PNP ID注册名单 2019-05-21
2019-05-02
【语言-c#】解析EDID
2019-05-02
【商业信息】E-EDID 标准
2019-05-02
【软件-Doxgen】工具:程序代码生成xml文档(doxgen)
2019-05-02
【框架-MFC】CMFCMenuBar 菜单按钮的图标添加
2019-05-02
【Windows】Win10 查找“组或用户名”为TrustedInstaller 对象
2019-05-02
【语言-c#】C# 注释详细介绍说明
2019-05-02
MySQL 内存模型
2019-05-02
Ubuntu下gyp简单入门实例
2019-05-02
express 解析post方式下的json参数
2019-05-02
node.js AES/ECB/PKCS5Padding 与其他语言的加密解密通用
2019-05-02
node.js 实现一个简单的登录拦截器
2019-05-02
c++抽象类、纯虚函数以及巧用纯虚析构函数实现接口类【转】
2019-05-02