树
深度优先搜索
二叉树
题目描述
给你一个二叉树的根节点 root
,计算并返回 整个树 的坡度 。
一个树的 节点的坡度 定义即为,该节点左子树的节点之和和右子树节点之和的 差的绝对值 。如果没有左子树的话,左子树的节点之和为 0 ;没有右子树的话也是一样。空结点的坡度是 0 。
整个树 的坡度就是其所有节点的坡度之和。
示例 1:
输入: root = [1,2,3]
输出: 1
解释:
节点 2 的坡度:|0-0| = 0(没有子节点)
节点 3 的坡度:|0-0| = 0(没有子节点)
节点 1 的坡度:|2-3| = 1(左子树就是左子节点,所以和是 2 ;右子树就是右子节点,所以和是 3 )
坡度总和:0 + 0 + 1 = 1
示例 2:
输入: root = [4,2,9,3,5,null,7]
输出: 15
解释:
节点 3 的坡度:|0-0| = 0(没有子节点)
节点 5 的坡度:|0-0| = 0(没有子节点)
节点 7 的坡度:|0-0| = 0(没有子节点)
节点 2 的坡度:|3-5| = 2(左子树就是左子节点,所以和是 3 ;右子树就是右子节点,所以和是 5 )
节点 9 的坡度:|0-7| = 7(没有左子树,所以和是 0 ;右子树正好是右子节点,所以和是 7 )
节点 4 的坡度:|(3+5+2)-(9+7)| = |10-16| = 6(左子树值为 3、5 和 2 ,和是 10 ;右子树值为 9 和 7 ,和是 16 )
坡度总和:0 + 0 + 0 + 2 + 7 + 6 = 15
示例 3:
输入: root = [21,7,14,1,1,2,2,3,3]
输出: 9
提示:
树中节点数目的范围在 [0, 104 ]
内
-1000 <= Node.val <= 1000
解法
方法一:递归
我们设计一个函数 $\text{dfs}$,用来计算以当前节点为根节点的子树的节点之和。在 $\text{dfs}$ 函数中,我们首先判断当前节点是否为空,若为空则返回 0。然后递归调用 $\text{dfs}$ 函数计算左子树的节点之和 $l$ 和右子树的节点之和 $r$。接着计算当前节点的坡度,即 $|l - r|$,并将其加到答案中。最后返回当前节点的节点之和 $l + r + \textit{root.val}$。
在主函数中,我们初始化答案为 0,然后调用 $\text{dfs}$ 函数计算整个树的坡度,并返回答案。
时间复杂度 $O(n)$,空间复杂度 $O(n)$。其中 $n$ 为节点的数量。
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution :
def findTilt ( self , root : Optional [ TreeNode ]) -> int :
def dfs ( root : Optional [ TreeNode ]) -> int :
if root is None :
return 0
l , r = dfs ( root . left ), dfs ( root . right )
nonlocal ans
ans += abs ( l - r )
return l + r + root . val
ans = 0
dfs ( root )
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 /**
* 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 {
private int ans ;
public int findTilt ( TreeNode root ) {
dfs ( root );
return ans ;
}
private int dfs ( TreeNode root ) {
if ( root == null ) {
return 0 ;
}
int l = dfs ( root . left ), r = dfs ( root . right );
ans += Math . abs ( l - r );
return l + r + root . val ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public :
int findTilt ( TreeNode * root ) {
int ans = 0 ;
auto dfs = [ & ]( this auto && dfs , TreeNode * root ) -> int {
if ( ! root ) {
return 0 ;
}
int l = dfs ( root -> left ), r = dfs ( root -> right );
ans += abs ( l - r );
return l + r + root -> val ;
};
dfs ( root );
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findTilt ( root * TreeNode ) ( ans int ) {
var dfs func ( * TreeNode ) int
dfs = func ( root * TreeNode ) int {
if root == nil {
return 0
}
l , r := dfs ( root . Left ), dfs ( root . Right )
ans += abs ( l - r )
return l + r + root . Val
}
dfs ( root )
return
}
func abs ( x int ) int {
if x < 0 {
return - x
}
return x
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 /**
* 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 {
let ans : number = 0 ;
const dfs = ( root : TreeNode | null ) : number => {
if ( ! root ) {
return 0 ;
}
const [ l , r ] = [ dfs ( root . left ), dfs ( root . right )];
ans += Math . abs ( l - r );
return l + r + root . val ;
};
dfs ( root );
return ans ;
}
GitHub