题目:给出一个二叉树,返回整个树的倾斜。
树节点的倾斜被定义为所有左子树节点值和所有右子树节点值之和的绝对差。 空节点有倾斜0。
整个树的倾斜度定义为所有节点倾斜的总和。
解题思路:一开始我就想错了,没有仔细看题目,其实题目不难,我想到了用一个全局变量来实现,但是一直在犹豫,想在一个函数里用递归全部解决,其实思路就是用另一个函数来递归加上所有的子节点的节点值,并且result全局变量收集每次的左节点和右节点的绝对差。
代码:
int result=0;
public int findTilt(TreeNode root) {
postorder(root);
return result;
}
public int postorder(TreeNode root){
if(root==null)return 0;
int left=postorder(root.left);
int right = postorder(root.right);
result+=Math.abs(left-right);
return right+left+root.val;
}
看了一眼别人的代码写的,高手的也是这样解决的。