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.
給定一二叉樹(shù)鸥跟，返回其整棵樹(shù)的傾斜度窃诉。
傾斜度定義為左子樹(shù)結(jié)點(diǎn)和與右子樹(shù)結(jié)點(diǎn)和的絕對(duì)值之差掂林∧关裕空節(jié)點(diǎn)的傾斜度為0照瘾。
整棵樹(shù)的傾斜度定義為所有結(jié)點(diǎn)傾斜度的和馅闽。
Example:
Input:
1
/ \
2 3
Output: 1
Explanation:
Tilt of node 2 : 0
Tilt of node 3 : 0
Tilt of node 1 : |2-3| = 1
Tilt 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.
思路
后序遍歷，遍歷過(guò)程中遞歸計(jì)算左右子樹(shù)的結(jié)點(diǎn)和熙参，同時(shí)使用全局變量記錄當(dāng)前節(jié)點(diǎn)傾斜度艳吠。
/**
* 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 {
private:
int res=0;
int postOrder(TreeNode* root){
if(!root) return 0;
int left=postOrder(root->left);
int right=postOrder(root->right);
res+=abs(left-right);
return left+right+root->val;
}
public:
int findTilt(TreeNode* root) {
postOrder(root);
return res;
}
};
或不使用全局變量，改為參數(shù)傳遞孽椰。
/**
* 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 {
private:
int postOrder(TreeNode* root, int& res){
if(!root) return 0;
int left=postOrder(root->left,res);
int right=postOrder(root->right,res);
res+=abs(left-right);
return left+right+root->val;
}
public:
int findTilt(TreeNode* root) {
int res=0;
postOrder(root,res);
return res;
}
};
