# 【leetcode刷题】T143-二叉树的坡度

`二叉树`类型第33篇解题报告

leetcode第563题：二叉树的坡度

https://leetcode-cn.com/problems/binary-tree-tilt

【题目】

```示例:

1
/   \
2     3

```

【思路】

1）假设我们有个函数能够实现求子树和的功能，那么怎么调用求得坡度呢？

```# 求得左右子树和
left = fun(node.left)
right = fun(node.right)
# 求得坡度
tilt = abs(left - right)
```

2）什么时候返回子树和呢？

```if not node:
return 0
left = ...
...
return left + right + node.val
```

【代码】

python版本

```# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def findTilt(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.tilt = 0
self.get_tilt(root)
return self.tilt

def get_tilt(self, node):
if not node:
return 0
left = self.get_tilt(node.left)
right = self.get_tilt(node.right)
print(node.val, left, right)
self.tilt += abs(left - right)
return left + right + node.val
```

C++版本

```/**
* 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 findTilt(TreeNode* root) {
int tilt = 0;
get_tilt(root, tilt);
return tilt;
}

int get_tilt(TreeNode* node, int& tilt){
if(!node)
return 0;
int left = get_tilt(node->left, tilt);
int right = get_tilt(node->right, tilt);
tilt += abs(left - right);
return left + right + node->val;
}
};```

189 篇文章25 人订阅

0 条评论