🌴 二叉树的坡度
📝 题目描述
给你一个二叉树的根节点root，计算并返回整个树的坡度。
一个树的节点的坡度定义即为，该节点左子树的节点之和和右子树节点之和的差的绝对值。如果没有左子树的话，左子树的节点之和为0；没有右子树的话也一样。空节点的坡度是0。
整个树的坡度就是其所有节点的坡度之和。
📋 代码模板
java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int findTilt(TreeNode root) {
}
}typescript
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function findTilt(root: TreeNode | null): number {
}💡 提示
树中节点数目的范围在
内
🚀 示例
🖊️ 题解
后序遍历
可惜没有如果
java
class Solution {
public int findTilt(TreeNode root) {
int[] tilt = new int[1];
dfs(root, tilt);
return tilt[0];
}
private int dfs(TreeNode node, int[] tilt) {
if (node == null) {
return 0;
}
int leftSum = dfs(node.left, tilt);
int rightSum = dfs(node.right, tilt);
tilt[0] += Math.abs(leftSum - rightSum);
return node.val + leftSum + rightSum;
}
}typescript
function findTilt(root: TreeNode | null): number {
const tilt: number[] = [0];
dfs(root, tilt);
return tilt[0];
}
function dfs(node: TreeNode | null, tilt: number[]): number {
if (node == null) {
return 0;
}
const leftSum = dfs(node.left, tilt);
const rightSum = dfs(node.right, tilt);
tilt[0] += Math.abs(leftSum - rightSum);
return leftSum + rightSum + node.val;
}