脚本宝典收集整理的这篇文章主要介绍了[LeetCode] Binary Tree Tilt，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
Binary Tree Tilt
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.
Divide and Conquer
Time Complexity
O(N)
Space Complexity
O(logn)
思路
这题给的example实在很confusing...举个栗子，这样的树返回的结果是11，所以我们要keep一个全局的result,一有结果就加，同时还要记录left subtree的sum 和right subtree的sum
1
/
2 3
/ /
4 5
代码
public int findTilt(TreeNode root) {
if(root == null) return 0;
int[] res = new int[]{0};
helper(root, res);
return res[0];
}
private int helper(TreeNode root, int[] res){
if(root == null) return 0;
int left = helper(root.left, res);
int right = helper(root.right, res);
res[0] += Math.abs(left - right);
return left + right + root.val;
}
以上是脚本宝典为你收集整理的[LeetCode] Binary Tree Tilt全部内容，希望文章能够帮你解决[LeetCode] Binary Tree Tilt所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。