首页 > 代码库 > 563 Binary Tree Tilt
563 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. 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.
这道题让我们求二叉树的坡度,某个结点的坡度的定义为该结点的左子树之和与右子树之和的差的绝对值,这道题让我们求所有结点的坡度之和. 这道题最好的解法应该是用后序遍历来做,因为后序遍历的顺序是左-右-根,那么就会从叶结点开始处理,这样我们就能很方便的计算结点的累加和,同时也可以很容易的根据子树和来计算tilt,
public class Solution { int ans = 0; public int findTilt(TreeNode root) { if (root == null) { return ans; } helper(root); return ans; } private int helper(TreeNode root) { if (root == null) { return 0; } int leftSum = helper(root.left); int rightSum = helper(root.right); ans += Math.abs(leftSum - rightSum); return leftSum + rightSum + root.val; } }
分治法原来就是后序遍历, 遍历到节点在处理, 然后返回到上层节点,
算法: 分治, 后序遍历( 在设计求 结点的左子树之和与右子树之和的基础上, 设计全局变量分治法求的差的绝对值)
容器: 全局变量, (要明白返回值是各个节点的子节点和, 而tilt 是总的, 都在变化, 只有子节点的可以当作返回值, 然后和是各个节点的tilt 和) 所以返回值的设定是子树的和!!
563 Binary Tree Tilt
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。