本文主要是介绍563. Binary Tree Tilt,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
563. 二叉树的坡度
给定一个二叉树,计算整个树的坡度。
一个树的节点的坡度定义即为,该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。
整个树的坡度就是其所有节点的坡度之和。
示例:
输入: 1/ \2 3 输出: 1 解释: 结点的坡度 2 : 0 结点的坡度 3 : 0 结点的坡度 1 : |2-3| = 1 树的坡度 : 0 + 0 + 1 = 1
注意:
- 任何子树的结点的和不会超过32位整数的范围。
- 坡度的值不会超过32位整数的范围。
解法一
//时间复杂度O(n), 空间复杂度O(1)
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:int getTilt(TreeNode* root, int& tilt) {if(!root) return 0;int suml = getTilt(root->left, tilt);int sumr = getTilt(root->right, tilt);tilt += abs(suml - sumr);return suml + sumr + root->val;}int findTilt(TreeNode* root) {int tilt = 0;getTilt(root, tilt);return tilt;}
};
思路:
后序遍历,函数getTilt返回值为树结点值的和,求和过程中对变量tilt作累计求和,遍历完成后返回tilt。
2019/06/02 22:21
这篇关于563. Binary Tree Tilt的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!