LeetCode C++ 563. Binary Tree Tilt【Tree/DFS】简单
发布日期:2021-07-01 02:52:18
浏览次数:3
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
留言是一种美德,欢迎回访!
[***.207.175.100]2024年04月10日 11时20分21秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Caffe 安装错误记录及解决办法【转】
2019-05-02
Android用类继承Application的全局变量使用注意
2019-05-02
qml之TextField使用笔记
2019-05-02
排序算法之冒泡排序
2019-05-02
排序算法之选择排序
2019-05-02
排序算法之希尔排序
2019-05-02
pyqt5之拖拽
2019-05-02
pyqt5之俄罗斯方块
2019-05-02
算法排序之堆排序
2019-05-02
算法排序之桶排序
2019-05-02
C++ Template函数模板参数(2.3节)
2019-05-02
lambda表达式初探
2019-05-02
C++11 bind函数
2019-05-02
C++ Template类模板的特化(3.3节, 3.4节)
2019-05-02
第05章 函数
2019-05-02
第08章 输入和输出
2019-05-02
第09章 异常处理
2019-05-02
第10章 面向对象编程
2019-05-02
第11章 案例研究: 文本统计
2019-05-02
qml drag listview
2019-05-02