题目序号 663、685、662、655、654、652、623

663. Equal Tree Partition

Given a binary tree with n nodes, your task is to check if it’s possible to partition the tree to two trees which have the equal sum of values after removing exactly one edge on the original tree.

Example 1:

Input:
  5
 / \
10 10
  /  \
 2   3

Output: True
Explanation:
5

/

10

Sum: 15

10

/

2 3

Sum: 15 Example 2:

Input:
1

/

2 10
/

2 20

Output: False Explanation: You can’t split the tree into two trees with equal sum after removing exactly one edge on the tree. Note:

The range of tree node value is in the range of [-100000, 100000]. 1 <= n <= 10000 题目大意： 给定二叉树，求是否存在一条边，将该边切断后得到的两个新二叉树的和相等。

解题思路： 递归求以各节点为根的子树的和

遍历各节点，判断该节点的子树和 * 2 == 根节点的节点和

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
def checkEqualTree(self, root):

“”” :type root: TreeNode :rtype: bool “”” self.dmap = {} def solve(n, c):

if not n: return 0 self.dmap[c] = n.val + solve(n.left, c * 2) + solve(n.right, c * 2 + 1) return self.dmap[c]

solve(root, 1) total = self.dmap[1] del self.dmap[1] return any(v * 2 == total for k, v in self.dmap.iteritems())

685. Redundant Connection II

In this problem, a rooted tree is a directed graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents.

The given input is a directed graph that started as a rooted tree with N nodes (with distinct values 1, 2, …, N), with one additional directed edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.

The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] that represents a directed edge connecting nodes u and v, where u is a parent of child v.

Return an edge that can be removed so that the resulting graph is a rooted tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array.

Example 1:

Input: [[1,2], [1,3], [2,3]] Output: [2,3] Explanation: The given directed graph will be like this:

1

/

v v 2–>3

Example 2:

Input: [[1,2], [2,3], [3,4], [4,1], [1,5]] Output: [4,1] Explanation: The given directed graph will be like this: 5 <- 1 -> 2

^ | | v 4 <- 3

Note: The size of the input 2D-array will be between 3 and 1000. Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.

662. Maximum Width of Binary Tree

Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a full binary tree, but some nodes are null.

The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the null nodes between the end-nodes are also counted into the length calculation.

Example 1:

Input:

1

/

3 2

/

5 3 9

Output: 4 Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).

Example 2:

Input:

1

/

3

/

5 3

Output: 2 Explanation: The maximum width existing in the third level with the length 2 (5,3).

Example 3:

Input:

1

/

3 2

/

5

Output: 2 Explanation: The maximum width existing in the second level with the length 2 (3,2).

Example 4:

Input:

1

/

3 2

/

5 9

/

6 7

Output: 8 Explanation:The maximum width existing in the fourth level with the length 8 (6,null,null,null,null,null,null,7).

Note: Answer will in the range of 32-bit signed integer.

654. Maximum Binary Tree

Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

The root is the maximum number in the array. The left subtree is the maximum tree constructed from left part subarray divided by the maximum number. The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.

Construct the maximum tree by the given array and output the root node of this tree.

Example 1:

Input: [3,2,1,6,0,5] Output: return the tree root node representing the following tree:

6

/

3 5
/
2 0
1

Note:

The size of the given array will be in the range [1,1000].

652. Find Duplicate Subtrees

Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them.

Two trees are duplicate if they have the same structure with same node values.

Example 1:
1

/

2 3

/ /

4 2 4
/

4

The following are two duplicate subtrees:
2

/

4

and
4

Therefore, you need to return above trees’ root in the form of a list.

623. Add One Row to Tree

Given the root of a binary tree, then value v and depth d, you need to add a row of nodes with value v at the given depth d. The root node is at depth 1.

The adding rule is: given a positive integer depth d, for each NOT null tree nodes N in depth d-1, create two tree nodes with value v as N’s left subtree root and right subtree root. And N’s original left subtree should be the left subtree of the new left subtree root, its original right subtree should be the right subtree of the new right subtree root. If depth d is 1 that means there is no depth d-1 at all, then create a tree node with value v as the new root of the whole original tree, and the original tree is the new root’s left subtree.

Example 1:

Input: A binary tree as following:

4

/

2 6

/ /

3 1 5

v = 1

d = 2

Output:
4

/

1 1

/

2 6

/ /

3 1 5

Example 2:

Input: A binary tree as following:

4

/

2

/

3 1

v = 1

d = 3

Output:
4

/

2

/

1 1

/

3 1

Note:

The given d is in range [1, maximum depth of the given tree + 1]. The given binary tree has at least one tree node.