vlambda博客
学习文章列表

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.

Example 1:

Input:

   3

  / \

 9  20

   /  \

  15   7

Output: [3, 14.5, 11]

Explanation:

The average value of nodes on level 0 is 3,  on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].

Note:

The range of node's value is in the range of 32-bit signed integer.

分析：

这里需要的是返回每一个层级的平均值。

因此，解决方法就是使用层序遍历一棵二叉树，然后对每个层级的二叉树取平均值。

细节问题：可以创建一个双端队列，保存当前层级的所有结点，并使用len获取当前层级的结点个数，然后依次遍历完各个层级的结点，再继续下一个层级的结点。

# 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 = rightimport collectionsclass Solution: def averageOfLevels(self, root: TreeNode) -> List[float]: que=[root] res=[] while que: n=len(que) sum=0 for i in range(n): node=que.pop(0) sum+=node.val if node.left: que.append(node.left) if node.right: que.append(node.right) res.append(sum/n) return res         # 第二种方法：使用DFS的方法，建立一个二维矩阵，每一行[x,y]分别保存每个层级的和值与结点数目，最后做平均处理即可。# DFSclass Solution: def averageOfLevels(self, root: TreeNode) -> List[float]: mat=[] def dfs(node,depth=0): if node: if len(mat) <=depth: mat.append([0,0]) mat[depth][0]+=node.val # sums up all values when traverse each node mat[depth][1]+=1 # every time traverse a node the number+1. dfs(node.left,depth+1) dfs(node.right,depth+1) dfs(root) return [s/n for s,n in mat]

Given a binary tree

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.

题目解释：

给定一颗二叉树，返回树的坡度。

单个节点的坡度定义为：

左子树的所有节点值之和与右子树的所有节点值之和的差值绝对值。

null节点可以视为0。

整棵树的坡度为，所有节点的坡度之和。

方法：

考虑递归的方法，当前节点的坡度为左子树之和与右子树之和的差值，通过递归的方式得到各个节点的坡度，并将结果存入数组中，最后求和处理(或者逐个将节点的坡度相加）

class Solution: def findTilt(self, root: TreeNode) -> int: self.ans=0
 def _sum(node): if not node: return 0 left, right= _sum(node.left),_sum(node.right) self.ans+=abs(left-right) return node.val+left+right
 _sum(root)
 return self.ans

。

分析：

将两棵二叉树叠加在一块，其中一棵树会覆盖另一棵。

其中会有重叠的结点，这些结点的合并规则为相加。

未重叠的结点则使用新的结点。

这里的话，需要同时遍历两棵二叉树，为了减少空间复杂度，直接在其中一棵树进行合并操作。

具体细节：

当两个结点均为空时，返回None。

当有一个结点为空时，使用另一个结点的值，若两个都不为空，则使用相加的值。

class Solution: def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode: if t1 and t2: t1.val+=t2.val t1.left=self.mergeTrees(t1.left,t2.left) t1.right=self.mergeTrees(t1.right,t2.right) return t1 else: return t1 or t2