题目

类型：Tree
image.png

解题思路

深度优先搜索
根据题意，需要累计二叉树中所有结点的左子树结点之和与右子树结点之和的差的绝对值。
可以使用深度优先搜索，在遍历每个结点时，累加其左子树结点之和与右子树结点之和的差的绝对值，并返回以其为根结点的树的结点之和。

具体地，实现算法如下：

  • 从根结点开始遍历，设当前遍历的结点为 node；
  • 遍历 node 的左子结点，得到左子树结点之和 sum_left；
  • 遍历 node 的右子结点，得到右子树结点之和 sum_right；
  • 将左子树结点之和与右子树结点之和的差的绝对值累加到结果变量 ans；
  • 返回以 node 作为根结点的树的结点之和 sum_left+sum_right+node.val。

代码

  1. public class BinaryTreeTilt {
  2.     int ans = 0;
  4.     public int findTilt(TreeNode root) {
  5.         dfs(root);
  6.         return ans;
  7.     }
  9.     public int dfs(TreeNode node) {
  10.         if (node == null) {
  11.             return 0;
  12.         }
  13.         int sumLeft = dfs(node.left);
  14.         int sumRight = dfs(node.right);
  15.         ans += Math.abs(sumLeft - sumRight);
  16.         return sumLeft + sumRight + node.val;
  17.     }
  18. }