\94. Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values.

Example:

1
2
3
4
5
6
7
8
Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]

Follow up: Recursive solution is trivial, could you do it iteratively?

Recursive version

1
2
3
4
5
6
class solution:
    def inorderTraversal(self, root:TreeNode) -> List[int]:
		if not root:
            return []
        else:
            return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)

Iterative Version

​ 中序遍历的递归定义为，先左子树，后根节点，然后右子树。

​ 因此，对于进入递归遍历路径一定是一直左子树，左子树，左子树，直到左子树为空，然后访问我们根节点，接着访问右子树，然后再进行左子树，左子树，左子树。。。

​ 所以我们对以上遍历方式进行用循环表示，前一部分依次访问左子树，可以用类似链表的方式一直迭代下去，依次访问右子树也一样。所以非递归的关键在如何访问根节点。因为二叉树并没有指向根节点的指针，因为在递归代码中，堆栈已经帮我们实现了弹出根节点这个功能。所以要非递归访问根节点，我们首先想到的是stack，那用stack存的是什么呢？当然是我们前面的左子树序列，当迭代到当前左子树为空时，我们访问当前根节点，然后访问右节点，然后继续迭代。。。

​ 所以代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def inorderTravelsal(self, root:TreeNode) -> List[int]:
        ans = []
        if root == None:
            return ans
        stack = []
        p = root
        while len(stack) > 0 and p != None:
            while p!= None:
                stack.append(p)
                p = p.next
            p = stack.pop()
            ans.append(p)
            p = p.right
        return ans

Morris Traversal（非递归，不用栈，Space：o(1)）

​ 使用了二叉树的变体，即线索化二叉树。

​ 具体做法呢，就是把所有所有右子节点的空指针改为指向下一个节点的指针，所以这样就不用回溯，也不用stack了。

​ 遍历二叉树最难的地方在于遍历完子节点如何重返父节点（因为没有指向父节点的指针）。所以无论是递归的程序栈还是非递归的节点栈都是为了解决这个问题。数据结构我们曾经学过二叉树线索化的概念，里面一个重要特性就是将前驱节点的右孩子设置为当前节点。这样我们在访问完前驱节点之后就可以直接像链表一样遍历当前节点（当然遍历之后要将右孩子重设为NULL）。但在Morris方法中不需要为每个节点额外分配指针指向其前驱（predecessor）和后继节点（successor），只需要利用叶子节点中的左右空指针指向某种顺序遍历下的前驱节点或后继节点就可以了。

​ 那基本思路就是在当前节点找到当前节点的前驱，并将其线索化，然后前驱变为当前节点，再找前驱，直到前驱为NULL，则输出。然后将前驱的后继作为当前节点。

​ 基本步骤如下：

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
33
1.若当前节点左孩子为空，则输出当前节点并将其右孩子作为当前节点。
2.若当前节点左孩子不为空，则在当前节点左子树中找到其中序遍历前驱节点
	a.若前驱节点右孩子为空，则右孩子指向当前节点，当前节点变为当前节点的左孩子。
	b.若前驱节点的右孩子为当前节点，则恢复为NULL，输出当前节点，当前节点变为当前节点的右孩子。

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

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        ans = []
        cur = root
        prev = None
        while cur != None:
            if cur.left == None:
                ans.append(cur.val)
                cur = cur.right
            else:
                prev = cur.left
                while prev.right != None and prev.right != cur:
                    prev = prev.right
                if prev.right == None:
                    prev.right = cur
                    cur = cur.left
                else: #将左子树里的前驱置为NULL,同时输出本节点，将本节点的右子节点作为cur
                    prev.right = None
                    ans.append(cur)
                    cur = cur.right
          return ans

\96. Unique Binary Search Trees

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

Example:

1
2
3
4
5
6
7
8
9
10
Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

本题实际上时Catalan Number的一个例子，至于这是个啥，大家可以查看wikipedia。一开始并没有发现这是个DP的题目，因为我看不出公式==。Anyway，拿到题目总归要有思路的切入点。这道题的切入点是什么呢？首先这是个二叉搜索树，二叉搜索树的核心性质是什么？——左子树所有节点一定小于根节点，右子树所有节点一定大于根节点。于是我们知道要形成不同的二叉树最基本的分类就是，所有的数字都做一遍根节点。当节点i坐根节点时，以上数字又被分为两部分，左边一堆全部小于i，右边一堆全部大于i。那么再对左右两堆节点再用同样的思路，所以最终的方案等于左边一堆的可以构建BST的个数乘以右边的可以构建BST的个数：

假设以i为根节点，可能的组合情况为F（i，n），而G（n）为输入n后的结果。则

F（i，n） = G（i-1）*G（n-i）

因为 i = 1~n，所以：

G（n） = F（1，n） + Ｆ（２，ｎ）　＋　……　＋Ｆ（ｎ，ｎ）

带入可得：

G(n) = G(0)G(n-1) + G(1)G(n-2) + … + G(n-1)G(0) (n个)

可以发现G(0) = 1(空树也是一种BST)

​ G(1) = 1

1
2
3
4
5
6
7
8
9
10
11
                 1                        n = 1        1

             2        1                   n = 2        2
            /          \
           1            2
  
1         3     3      2      1           n = 3        5
 \       /     /      / \      \
  3     2     1      1   3      2
 /     /       \                 \
2     1         2                 3

代码如下：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
       def numTrees(self, n: int) -> int:
           if n <= 1:
               return 1
           dp = [0] * n+1
           dp[0] = 1
           dp[1] = 1
           for num in range(2, n+1):# 左子树与右子树乘积的种类个数
               for i in range(num):
                   dp[num] += dp[i] * dp[num-i-1]
           return dp[n]

[Complexity Analysis]

Time complexity: O(n²)

Space complexity: O(n)

\95. Unique Binary Search Trees II

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 … n.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Input: 3
Output:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Recursive Vesion

递归的想法比较直观，即把每个数作为root，根据root，把数分成两堆，然后这两堆分别构造BST，退出Recursion为左边界大于等于右边界。

递归方法一：每一个递归调用定义一个list，用来收集子树的不同类型，然后最后与当前root进行遍历组合。然后返回递归调用。

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        if n <= 0:
            return []
        return self.generate(1, n)
    def generate(self, left, right):
        l = []
        if left > right:
            l.append(None)
        for k in range(left, right+1):
            left_n = self.generate(left, k-1)
            right_n = self.generate(k+1, right)
        	for nodeleft in left_n:
                for noderight in right_n:
                    root = TreeNode(k)
                    root.left = nodeleft
                    root.right = noderight
                    l.append(root)
        return l

上面的方法速度实际是有缺陷的，因为存在重复构造BST的行为，如会多次出现构造同样大小[left,right]的子列表。所以改进方法就是引入memory机制，即：dynamic programming memoization。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
	def __init__(self):
        self.memo = {}
    def generateTrees(self, n: int) -> List[TreeNode]:
        if n <= 0:
            return []
        return self.generate(1, n)
    def generate(self, left, right):
        if (left, right) not in memo:
            if left > right:
                return [None]
        	out = []
            for k in range(left, right+1):
                left_n = self.generate(left, k-1)
                right_n = self.generate(k+1, right)
                for nodeleft in left_n:
                    for noderight in right_n:
                        root = TreeNode(k)
                        root.left = nodeleft
                        root.right = noderight 
                        out.append(root)
           self.memo[(left, right)] = out
        return memo[(left, right)]

DP version

这个以后补充

\99. Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Input: [1,3,null,null,2]

   1
  /
 3
  \
   2

Output: [3,1,null,null,2]

   3
  /
 1
  \
   2

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Input: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

Output: [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3

Follow up:

  • A solution using O(n) space is pretty straight forward.
  • Could you devise a constant space solution?

基本的方法，中序遍历BST，构造两个列表，分别存储节点和节点值，对节点值列表排序，将节点值依次赋值给节点：

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        node_list = []
        val_list = []
        self.inorder(root, node_list, val_list)
        val_list = sorted(val_list)
        for i in range(len(val_list)):
            node_list[i].val = val_list[i]
    def inorder(self, root, node_list, val_list):
        if not root:
            return 
        inorder(root.left, node_list, val_list)
        node_list.append(root)
        val_list.append(root.val)
        inorder(root.right, node_list, val_list)

但是这种方法时间复杂度，空间复杂度都没有满足Follow up

法二（不用两个列表做数据结构，用两个指针替换)有递归和非递归的方法：

1
2
3
4
5
6
7
8
9
10
#recusive
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def recoverTree(self, root: TreeNode) -> None:

法三：Morris遍历

\100. Same Tree

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

1
2
3
4
5
6
7
Input:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true

Example 2:

1
2
3
4
5
6
7
Input:     1         1
          /           \
         2             2

        [1,2],     [1,null,2]

Output: false

Example 3:

1
2
3
4
5
6
7
Input:     1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

Output: false

​ 这道题的思路就是两个树同时用同一种方式遍历，若相等 则是一样的。同一种遍历方式代表了结构相同，是否相等则代表判断节点的值。

Recursive:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        if p and not q or not p and q or p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Intertive:

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:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def check(self, p, q):
        if not p and not q:
            return True
        if not p or not q:
            return False
        if p.val != q.val:
            return False
        return True 
    
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        seq = [(p, q)]
        while len(seq) > 0:
            p, q = seq.pop(0)
            if not self.check(p, q):
                return False
            if p:
                seq.append((p.left, q.left))
                seq.append((p.right, q.right))
        return True

\101. Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

1
2
3
4
5
    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

1
2
3
4
5
  1
 / \
2   2
 \   \
 3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

递归思路：如果是对称树的话，根左右和根右左遍历应该是一样的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        return self.check(root, root)
    def check(self, root1, root2):
        if not root1 and not root2:
            return True
        if not root1 or not root2:
            return False
        if root1.val != root2.val:
            return False
        return self.check(root1.left, root2.right) and self.check(root1.right, root2.left)

迭代思路：广度优先，使用两个队列，分别存储两个左右孩子作为根的树，判断两个队列是否对称

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if root == None:
            return True
        left = []
        right = []
        while(len(left) > 0):
            l = left.pop(0)
            r = right = pop(0)
            if not left and not right:
                continue
            if not left or not right or l.val != r.val:
                return False
            left.append(l.left)
            left.append(l.right)
            right.append(r.right)
            right.append(r.left)
        return True

\102. Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

return its level order traversal as:

1
2
3
4
5
[
  [3],
  [9,20],
  [15,7]
]
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
33
34
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if root == None:
            return []
        ans = []
        que = [root]
        t = []

        currentcount = 1
        nextcount = 0
        while len(que) > 0:
            x = que.pop(0)
            t.append(x.val)
            if x.left:
                que.append(x.left)
                nextcount += 1
            if x.right:
                que.append(x.right)
                nextcount += 1
            currentcount -= 1

            if currentcount == 0:
                ans.append(t)
                t = []
                currentcount = nextcount 
                nextcount = 0
        return ans

\103. Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

return its zigzag level order traversal as:

1
2
3
4
5
[
  [3],
  [20,9],
  [15,7]
]

思路：第一层 3

​ 第二层 20 9

​ 第三层15 7

​ 符合后进先出的性质，用栈。同时我们发现偶数层子节点入栈为先左再右，奇数层为先右再左。所以用两个栈 。

​ 

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
33
34
35
36
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        ans = []
        stacks = [[],[]]
        temp = []
        current = 0
        nex = 1
        stacks[current].append(root)
        while len(stacks[0]) > 0 or len(stacks[1]) > 0:
            x = stack[current].pop()
            temp.append(x.val)
            if current == 0:
                if x.right:
               		stacks[nex].append(x.right)
                if x.left:
                    stacks[nex].append(x.left)
            else:
                if x.left:
                    stacks[nex].append(x.left)
                if x.right:
                    stacks[nex].append(x.right)
            if len(stacks[current]) == 0:
                current = 1 - current
                nex = 1 - next
                ans.append(temp)
                temp = []
        return ans

\116. Populating Next Right Pointers in Each Node

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

1
2
3
4
5
6
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Follow up:

  • You may only use constant extra space.
  • Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem.

Example 1:

img

1
2
3
Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Constraints:

  • The number of nodes in the given tree is less than 4096.
  • -1000 <= node.val <= 1000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return None
        ans = root
        while root.left:
            cur = root
            while(cur):
                cur.left.next = cur.right
                if cur.next:
                    cur.right.next = cur.next.left
                cur = cur.next
            root = root.left
        return ans

下面是一个递归的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root or not root.left and not root.right:
            return
        p = root.left
        q = root.right
        p.next = q.right
        while not p.right:
            p = p.right
            q = q.left
            p.next = q
        
        self.connect(root.left)
        self.connect(root.right)

\117. Populating Next Right Pointers in Each Node II

Given a binary tree

1
2
3
4
5
6
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Follow up:

  • You may only use constant extra space.
  • Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem.

Example 1:

img

1
2
3
Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Constraints:

  • The number of nodes in the given tree is less than 6000.
  • -100 <= node.val <= 100

思路一：每一层设置一个头结点，两个循环，若父节点root，存在左子节点，则连接并指向它，循环。若父节点有next，则指向它，按上一步循环。

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
33
34
35
36
37
38
39
40
41
42
"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""
#O(n)space
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        head = root
        while root:
            cur = dummy = ListNode(0)
            while root:
                if root.left:
                    cur.next = root.left
                    cur = cur.root.left
                if root.right:
                    cur.next = root.right
                    cur = root.right
                root = root.next
            root = dummy.next
        return head
#O(1)space
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        head = root
        tail = dummy = ListNode(0)
        while root:
            tail.next = root.left
            if tail.next:
                tail = tail.next
            tail.next = root.right
            if tail.next:
                tail = tail.next
            root = root.next
            if not root:
                tail = dummy
                root = dummy.next
        return head

\124. Binary Tree Maximum Path Sum

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:

1
2
3
4
5
6
7
Input: [1,2,3]

       1
      / \
     2   3

Output: 6

Example 2:

1
2
3
4
5
6
7
8
9
Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

思路：本题的路径是指从树的底部或更高向上走，然后到达某个结点再往下走，一定那向下就不能返回。“某个结点”就是最高结点。也就是路径上所有其他结点的最低公共祖先。本题递归计算当前最高点的左路径和右路径加结点值之和，看是否大于Max_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
class Solution:
    max_val = -float("inf")
    def maxPathSum(self, root):
        self.maxPathDown(root)
        return self.max_val
    def maxPathDown(self, node):
        if not node:
        	return 0
    	left = max(0, self.maxPathDown(node.left))
        right = max(0, self.maxPathDown(node.right))
        self.max_val = max(self.max.val, left + right + node.val)
        return node.val + max(left, right)
class Solution:
    max_val = -float("inf")
    def maxPathSum(self, root):
        self.maxPathDown(root)
        return self.max_val
    def maxPathDown(self, node):
        if not node:
            return 0
        left = self.maxPathDown(node.left)
        right = self.maxPathDown(node.right)
        temp = root.val + left + right
        sum_val = root.val + max(left ,right, 0)
        self.max_val = max(sum_val, temp, self.max_val)
        return sum_val

\129. Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

Note: A leaf is a node with no children.

Example:

1
2
3
4
5
6
7
8
9
Input: [1,2,3]
    1
   / \
  2   3
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12
Input: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        return self.get_numbers(root, 0)
    def get_numbers(self, root, cur_sum):
        if not root:
            return 0
        cur_sum = cur_sum*10 + root.val
        if not root.left and not root.right:
            return cur_sum
        return self.get_numbers(root.left, cur_sum) + self.get_numbers(root.right, cur_sum)
    
class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        self.res = 0
        self.get_numbers(root, 0)
        return self.res
    def get_numbers(self, root, cur_sum):
        if root:
            self.get_numbers(root.left, cur_sum*10 + root.val)
            self.get_numbers(root.right, cur_sum*10 + root.val)
            if not root.left and not root.right:
                self.res += cur_sum*10 + root.val

\144. Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes’ values.

Example:

1
2
3
4
5
6
7
8
Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,2,3]

Follow up: Recursive solution is trivial, could you do it iteratively?

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
#Recursive
class Solution:
    ans = []
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return
        self.ans.append(root.val)
        self.preorderTraversal(root.left)
        self.preorderTraversal(root.right)
        return self.ans
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
		res = []
        self.dfs(root, res)
        return res
   	def dfs(self, root, res):
        if root:
            res.append(res.val)
            self.dfs(root.left, res)
            self.dfs(root.right, res)
#Iterative
class Solution:
    def preorderTravelsal(self, root):
        out = []
        stack = [root]
        while stack:
            temp = stack.pop()
            if temp:
                out.append(temp.val)
            stack.append(root.right)
            stack.append(root.left)
        return out

\144. Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes’ values.

Example:

1
2
3
4
5
6
7
8
Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,2,3]

Follow up: Recursive solution is trivial, could you do it iteratively?

1
2


\173. Binary Search Tree Iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Example:

img

1
2
3
4
5
6
7
8
9
10
BSTIterator iterator = new BSTIterator(root);
iterator.next();    // return 3
iterator.next();    // return 7
iterator.hasNext(); // return true
iterator.next();    // return 9
iterator.hasNext(); // return true
iterator.next();    // return 15
iterator.hasNext(); // return true
iterator.next();    // return 20
iterator.hasNext(); // return false

Note:

  • next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
  • You may assume that next() call will always be valid, that is, there will be at least a next smallest number in the BST when next() is called.
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
33
34
35
36
37
38
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class BSTIterator:

    def __init__(self, root: TreeNode):
        self.stack = []
        self.pushAll(root)

    def next(self) -> int:
        """
        @return the next smallest number
        """
        if self.hasNext():
            tmp = self.stack.pop()
            self.pushAll(tmp.right)
            return tmp.val
    def hasNext(self) -> bool:
        """
        @return whether we have a next smallest number
        """
        return self.stack
    
    def pushAll(self, node):
        while node is not None:
            self.stack.append(node)
            node = node.left
        


# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()

\199. Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example:

1
2
3
4
5
6
7
8
9
Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

思路：大佬的neat solution

(1) the traverse of the tree is NOT standard pre-order traverse. It checks the RIGHT node first and then the LEFT
(2) the line to check currDepth == result.size() makes sure the first element of that level will be added to the result list
(3) if reverse the visit order, that is first LEFT and then RIGHT, it will return the left view of the tree.

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        result = []
        self.right_view(root, result, 0)
        return result
    def right_view(self, cur, result, cur_dep):
        if not cur:
            return 
        if cur_dep == len(result):
            result.append(cur.val)
        self.right_view(cur.right, result, cur_dep + 1)
        self.right_view(cur.left, result, cur_dep + 1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#iterative
class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
    	result = []
        que = []
        if not root:
            return result
        que.append(root)
        while que:
            result.append(que[-1].val)
            n = len(que)
            while n > 0:
                tmp = que.pop(0)
                if tmp.left:
                    que.append(tmp.left)
                if tmp.right:
                    que.append(tmp.right)
                n -= 1
        return result

\222. Count Complete Tree Nodes

Given a complete binary tree, count the number of nodes.

Note:

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Example:

1
2
3
4
5
6
7
8
Input: 
    1
   / \
  2   3
 / \  /
4  5 6

Output: 6

思路：

  1. If left sub tree height equals right sub tree height then,
    a. left sub tree is perfect binary tree
    b. right sub tree is complete binary tree
  2. If left sub tree height greater than right sub tree height then,
    a. left sub tree is complete binary tree
    b. right sub tree is perfect binary tree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def countNodes(self, root: TreeNode) -> int:
        if not root:
            return 0
        left_depth = self.get_depth(root.left)
        right_depth = self.get_depth(root.right)
        if left_depth == right_depth:
            return pow(2, left_depth) + self.countNodes(root.right)
        else:
            return pow(2, right_depth) + self.countNodes(root.left)
        
        def get_depth(self, root):
            if not root:
                return 0
            return 1 + self.get_depth(root.left)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def countNodes(self, root: TreeNode) -> int:
        if not root:
            return 0
        l = r = root
        l_h = r_h = 0
        while l:
            l = l.left
            l_h += 1
        while r:
            r = r.right
            r_h += 1
        if l_h == r_h:
            return pow(2, l_h) - 1
        else:
            return 1 + self.countNodes(root.left) + self.countNodes(root.right)

\297. Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Example: 

1
2
3
4
5
6
7
8
9
You may serialize the following tree:

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]"

Clarification: The above format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

思路：遍历二叉树与重构二叉树

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
class Codec:
    def serialize(self, root):
        preorder = ""
        if not root:
            preorder += ",None"
        preorder += "," + str(root.val)
        preorder += self.serialize(root.left)
        preorder += self.serialize(root.right)
        return preorder
    
    def deserialize(self, data):
        data = data[1:].split(",")
        for i in range(len(data)):
            if data[i] == "None":
                data[i] == None
            else:
                data[i] = int(data[i])
        root = self.buildTree(data)
        return root
    
    def buildTree(self, data):
        if len(data) == 0:
            return 
        if data[0] == None:
            return data.pop(0)
        
        root = TreeNode(data.pop(0))
        root.left = self.buildTree(data)
        root.right = self.buildTree(data)
        return root

\337. House Robber III

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

1
2
3
4
5
6
7
8
9
10
Input: [3,2,3,null,3,null,1]

     3
    / \
   2   3
    \   \ 
     3   1

Output: 7 
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

1
2
3
4
5
6
7
8
9
10
Input: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \ 
 1   3   1

Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.
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
33
34
35
36
37
38
39
40
41
42
43
class Solution:
    def rob(self, root: TreeNode) -> int:
        if not root:
            return 0
        val = 0
        if root.left:
           val += self.rob(root.left.left) + self.rob(root.left.right)
        if root.right:
            val += self.rob(root.right.left) + self.rob(root.right.right)
        return max(root.val + val, self.rob(root.left) + self.rob(root.right))
    
#里面有大量重复计算，计算超时
#记忆力机制

class Solution:
    def rob(self, root: TreeNode) -> int:
        if not root:
            return 0
        if root in self.map:
            return self.map[root]
        val = 0
        if root.left:
            val += self.rob(root.left.left) + self.rob(root.left.right)
        if root.right:
            val += self.rob(root.right.left) + self.rob(root.right.right)
        val = max(root.val + val, self.rob(root.left) + self.rob(root.right))
        self.map[root] = val
        return val
 
class Solution:
    def rob(self, root):
        res = self.subrob(root)
        return max(res[0], res[1])
    def subrob(self, root):
        if not root:
            return [0, 0]
        left = self.subrob(root.left)
        right = self.subrob(root.right)
        
        res = [0, 0]
        res[0] = max(left[0], left[1]) + max(right[0], right[1])
        res[1] = root.val + left[0] + right[0]
        return res

\404. Sum of Left Leaves

Find the sum of all left leaves in a given binary tree.

Example:

1
2
3
4
5
6
7
    3
   / \
  9  20
    /  \
   15   7

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

思路：本题可采用前序遍历，需要我们判定左结点，可以设置一个tag，递归下去的时候用来指示是否为左子树，因此剩下只需要判定是不是叶子结点就可以了（左右子树同时为空）。

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
class Solution:
    def __init__(self):
        self.ans = 0
    def sumOfLeftLeaves(self, root: TreeNode) -> int:
        self.dfs(root)
        return self.ans
    def dfs(self, root, left = False):
        if not root:
            return 0
        if left and not root.left and not root.right:
            self.ans += root.val
        self.dfs(root.left, True)
        self.dfs(root.right)
        
#不需要全局变量
class Solution:
    def sumOfLeftLeaves(self.root):
        if not root:
            return 0
        if root.left:
            if not root.left.left and not root.left.right:
                ans += root.left.val
             else:
                ans += self.sumOfLeftLeaves(root.left)
        ans += self.sumOfLeftLeaves(root.right)
        return ans

\1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly\ one solution, and you may not use the same element twice.

Example:

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

思路：本题提供了一个经典的hashmap用法，那就在遍历当前值时，计算目标值与当前值的差，看是否在之前遍历过的元素里。

代码如下：

1
2
3
4
5
6
7
8
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        m = dict()
        for i in range(len(nums)):
            if (target - nums[i]) in m:
                return [i, m[target-nums[i]]]
            m[nums[i]] = i
        return []

\437. Path Sum III

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

思路一：前面的题目112中，我们会做给定二叉树从根节点到路径的节点和是否为给定值。以此为基础，我们可以想到：对每一个结点作为根节点暴力遍历，则可以解决这个问题，代码如下：

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.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    
    def pathSum(self, root: TreeNode, sum: int) -> int:
        self.n = 0
        self.dfs(root, sum)
        return self.n
    def dfs(self, root, sum):
        if not root:
            return 
        self.test(root, sum)
        self.dfs(root.left, sum)
        self.dfs(root.right, sum)
        
    def test(self, root, sum):
        if not root:
            return None
        
        if sum == root.val:
            self.n += 1
        self.test(root.left, sum - root.val)
        self.test(root.right, sum - root.val)

​ 我们可以看到代码中存在很多重复计算，如计算1–3–5，这条路径，你需要计算1， 1+3， 3， 1+3+5， 3+5， 5。我们可以借鉴上一题two sum的方法，引入记忆化方法：在一条路径上，依次计算根节点到当前值的和，如果当前值的和减去目标值的结果在hashmap中，则说明路径上有相应的路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def pathSum(self, root, target):
        self.result = 0
        cache = {0: 1}
        self.dfs(root, target, 0, cache)  
        return self.result
    
    def dfs(self, root, target, cur_sum, cache):
        if not root:
            return 
        cur_sum += root.val
        old_sum = cur_sum - target
        self.result += cache.get(old_sum, 0)
        cache[cur_sum] = cache.get(cur_sum, 0) + 1
        
        self.dfs(root.left, target, cur_sum, cache)
        self.dfs(root.right, target, cur_sum, cache)
        cache[cur_sum] -= 1

\450. Delete Node in a BST

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

  1. Search for a node to remove.
  2. If the node is found, delete the node.

Note: Time complexity should be O(height of tree).

Example:

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
root = [5,3,6,2,4,null,7]
key = 3

    5
   / \
  3   6
 / \   \
2   4   7

Given key to delete is 3. So we find the node with value 3 and delete it.

One valid answer is [5,4,6,2,null,null,7], shown in the following BST.

    5
   / \
  4   6
 /     \
2       7

Another valid answer is [5,2,6,null,4,null,7].

    5
   / \
  2   6
   \   \
    4   7
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
class Solution:
    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
        if not root:
            return root
        if root.val < key:
            root.right = self.deleteNode(root.right, key)
        elif root.val > key:
            root.left = self.deleteNode(root.left, key)
        else:
            if not root.left:
                return root.right
            elif not root.right:
                return root.left
            else:
                new_root = root.right
                cur = None
                while new_root.left:
                    cur = new_root
                    new_root = new_root.left
                if cur == None:
                    new_root.left = root.left
                    return new_root

                cur.left = new_root.right
                new_root.left = root.left
                new_root.right = root.right
                return new_root
        return root

\508. Most Frequent Subtree Sum

Given the root of a tree, you are asked to find the most frequent subtree sum. The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself). So what is the most frequent subtree sum value? If there is a tie, return all the values with the highest frequency in any order.

Examples 1
Input:

1
2
3
  5
 /  \
2   -3

return [2, -3, 4], since all the values happen only once, return all of them in any order.

Examples 2
Input:

1
2
3
  5
 /  \
2   -5

return [2], since 2 happens twice, however -5 only occur once.

Note: You may assume the sum of values in any subtree is in the range of 32-bit signed integer.

思路：递归和Hashmap.遍历求每个子树的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def __init__(self):
        self.maxCount = 0
        self.count = dict()
    
    def findFrequentTreeSum(self, root: TreeNode) -> List[int]:
        self.dfs(root)
        res = []
        for k_v in self.count.items():
            if k_v[1] == self.maxCount:
                res.append(k_v[0])
        return res                                                            
        
    def dfs(self, root):
        if not root:
            return 0
        s = self.dfs(root.left) + self.dfs(root.right) + root.val
        if not self.count.get(s, 0):
            self.count[s] = 0
        self.count[s] += 1
        self.maxCount = max(self.maxCount, self.count[s])        
        return s

\513. Find Bottom Left Tree Value

Given a binary tree, find the leftmost value in the last row of the tree.

Example 1:

1
2
3
4
5
6
7
8
Input:

    2
   / \
  1   3

Output:
1

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12
Input:

        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7

Output:
7

Note: You may assume the tree (i.e., the given root node) is not NULL.

思路一：这个思路比较巧妙，从右向左层序遍历二叉树，最后一个元素就是最左侧元素

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def findBottomLeftValue(self, root: TreeNode) -> int:
        if not root:
            return None
        queue = [root]
        while(queue):
            end = queue.pop(0)
            if end.right:
                queue.append(end.right)
            if end.left:
                queue.append(end.left)
        return end.val

思路二：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def findBottomLeftValue(self, root):
        """
        :type root: TreeNode
        :rtype:
        """
        r = [None, 0]
        def search(node, depth):
            if not node:
                return 
            if depth >= r[1]: #注意有等号，表示最左！！！
                r[0] = node.val
                r[1] = depth
            search(node.right, depth+1)
            search(node.left, depth+1)
        search(root, 1)
        return r[0]

\515. Find Largest Value in Each Tree Row

You need to find the largest value in each row of a binary tree.

Example:

1
2
3
4
5
6
7
8
9
Input: 

          1
         / \
        3   2
       / \   \  
      5   3   9 

Output: [1, 3, 9]
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
33
34
#BFS
class Solution:
    def largestValues(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        queue = [root]
        num = 1
        res = [root.val]
        while(queue):
            if num == 0:
                res.append(max([i.val for i in queue]))
                num = len(queue)
            n = queue.pop(0)
            num -= 1
            if n.left:
                queue.append(n.left)
            if n.right:
                queue.append(n.right)
        return res
#DFS
class Solution:
    def largestValues(self, root: TreeNode) -> List[int]:
        self.ans = []
        self.helper(root, 0)
        return self.ans
    def helper(self, node, level):
        if not node:
            return 
        if len(self.ans) == level:
            self.ans.append(node.val)
        else:
            self.ans[level] = max(self.ans[level], node.val)
        self.helper(node.left, level+1)
        self.helper(node.right, level+1)

\530. Minimum Absolute Difference in BST

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
Input:

   1
    \
     3
    /
   2

Output:
1

Explanation:
The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).

Note: There are at least two nodes in this BST.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def __init__(self):
        self.min = float("inf")
        self.prev = None
    def getMinimumDifference(self, root: TreeNode) -> int:
        if not root:
            return self.min
        self.getMinimumDifference(self.left 
        if self.prev != None:
            self.min = min(self.min, root.val-self.prev)
        self.prev = root.val
        self.getMinimumDifference(root.right)
        return self.min

\538. Convert BST to Greater Tree

Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

Example:

1
2
3
4
5
6
7
8
9
Input: The root of a Binary Search Tree like this:
              5
            /   \
           2     13

Output: The root of a Greater Tree like this:
             18
            /   \
          20     13
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def __init__(self):
        self.prev = None
    def convertBST(self, root: TreeNode) -> TreeNode:
        if not root:
            return 
        self.convertBST(root.right)
        if self.prev != None:
            root.val += self.prev
        self.prev = root.val
        self.convertBST(root.left)
        return root

\543. Diameter of Binary Tree

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree

1
2
3
4
5
    1
   / \
  2   3
 / \     
4   5

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

思路：It took me a while to figure this out. The code is correct but the explanation is clearly wrong. So although the longest path doesn’t have to go through the root node, it has to pass the root node of some subtree of the tree (because it has to be from one leaf node to another leaf node, otherwise we can extend it for free). The longest path that passes a given node as the ROOT node is T = left_height+right_height. So you just calculate T for all nodes and output the max T.

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        ans = [0]
        self.depth(root, ans)
        return ans[0]
    def depth(self, root, ans):
        if not root:
            return 0
        left = self.depth(root.left, ans)
        right = self.depth(root.right, ans)
        ans[0] = max(ans[0], left+right)
        return 1 + max(left, right)

\563. Binary Tree Tilt

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:

1
2
3
4
5
6
7
8
9
10
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:

  1. The sum of node values in any subtree won’t exceed the range of 32-bit integer.

  2. All the tilt values won’t exceed the range of 32-bit integer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def findTilt(self, root: TreeNode) -> int:
        self.ans = [0]
        self.helper(root)
        return self.ans[0]
    def helper(self, root):
        if not root:
            return 0
        left = self.helper(root.left)
        right = self.helper(root.right)
        
        self.ans[0] += abs(left - right)
        
        return root.val + left + right

\572. Subtree of Another Tree

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.

Example 1:
Given tree s:

1
2
3
4
5
    3
   / \
  4   5
 / \
1   2

Given tree t:

1
2
3
  4 
 / \
1   2

Return true, because t has the same structure and node values with a subtree of s.

Example 2:
Given tree s:

1
2
3
4
5
6
7
    3
   / \
  4   5
 / \
1   2
   /
  0

Given tree t:

1
2
3
  4
 / \
1   2

Return false.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        if not s:
            return False
        if self.is_same(s, t):
            return True
        return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)
    def is_same(self, s, t):
        if not s and not t:
            return True
        if not s or not t:
            return False
        if s.val != t.val:
            return False
        return self.is_same(s.left, t) and self.is_same(s.right, t)

本题与剑指offer上的题目树的子结构类似。不同的是那道题目子结构只需要树s的一部分与t相同即可。而本题则要求是子树。

剑指offer源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        result = False
        if not s and not t:
            if s.val == p.val:
                self.check(s, t)
            if not result:
                result = self.isSubtree(s.left, t)
            if not result:
                result = self.isSubtree(s.right, t)
        return result
    def check(self, s, t):
        if not s:
            return False
        if not t:
            return True
        if s.val != t.val:
            return False
        return self.check(s.left, t.left) and self.check(s.right, t.right)

\606. Construct String from Binary Tree

You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way.

The null node needs to be represented by empty parenthesis pair “()”. And you need to omit all the empty parenthesis pairs that don’t affect the one-to-one mapping relationship between the string and the original binary tree.

Example 1:

1
2
3
4
5
6
7
8
9
Input: Binary tree: [1,2,3,4]
       1
     /   \
    2     3
   /    
  4     

Output: "1(2(4))(3)"
Explanation: Originallay it needs to be "1(2(4)())(3()())", but you need to omit all the unnecessary empty parenthesis pairs. And it will be "1(2(4))(3)".

Example 2:

1
2
3
4
5
6
7
8
9
Input: Binary tree: [1,2,3,null,4]
       1
     /   \
    2     3
     \  
      4 

Output: "1(2()(4))(3)"
Explanation: Almost the same as the first example, except we can't omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def tree2str(self, t: TreeNode) -> str:
        if not t:
            return ""
        result = str(t.val)
        left = self.tree2str(t.left)
        right = self.tree2str(t.right)
        
        if left == "" and right == "":
            return result
        if left == "":
            return result + "()" + "(" + right + ")"
        if right == "":
            return result + "(" + left + ")"
        return result + "(" + left + ")" + "(" + right + ")"

\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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Input: 
A binary tree as following:
      4
     /   
    2    
   / \   
  3   1    

v = 1

d = 3

Output: 
      4
     /   
    2
   / \    
  1   1
 /     \  
3       1

Note:

  1. The given d is in range [1, maximum depth of the given tree + 1].
  2. The given binary tree has at least one tree node.
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#BFS
class Solution:
    def addOneRow(self, root: TreeNode, v: int, d: int) -> TreeNode:
        if d == 1:
            node = TreeNode(v)
            node.left = root
            return node
        queue = [root]
        for _ in range(d-2):
            size = len(queue)
            for i in range(size):
                if queue[0].left:
                    queue.append(queue[0].left)
                if queue[0].right:
                    queue.append(queue[0].right)
                queue.pop(0)
        for i in queue:
            tmp = TreeNode(v)
            tmp.left = i.left
            i.left = tmp
            tmp = TreeNode(v)
            tmp.right = i.right
            i.right = tmp
        return root
#DFS
class Solution:
    def addOneRow(self, root: TreeNode, v: int, d: int) -> TreeNode:
        if d == 1:
            newroot = TreeNode(v)
            newroot.left = root
            return newroot
        self.dfs(root, 1, v, d)
        return root
    def dfs(self, root, depth, v, d):
        if not root:
            return None
        if depth < d-1:
            self.dfs(root.left, depth+1, v, d)
            self.dfs(root.right, depth+1, v, d)
        else:
            tmp = TreeNode(v)
            tmp.left = root.left
            root.left = tmp
            tmp = TreeNode(v)
            tmp.right = root.right
            root.right = tmp

\637. Average of Levels in Binary Tree

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

Example 1:

1
2
3
4
5
6
7
8
9
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:

  1. The range of node’s value is in the range of 32-bit signed integer.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def averageOfLevels(self, root: TreeNode) -> List[float]:
        count = []
        avgs = []
        self.average(root, count, avgs, 0)
        print(count, avgs)
        return [i[1]/i[0] for i in zip(count, avgs)]
        
    def average(self, root, count, sums, l):
        if root == None:
            return
        # print(l, len(sums))
        if l > len(sums)-1:
            sums.append(0)
            count.append(0)
        # print(sums)
        sums[l] += root.val
        count[l] += 1
        # print(sums)
        self.average(root.left, count, sums, l+1)
        self.average(root.right, count, sums, l+1)

\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
5
6
7
    1
   / \
  2   3
 /   / \
4   2   4
   /
  4

The following are two duplicate subtrees:

1
2
3
  2
 /
4

and

1
4

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

思路：将每一个子树序列化存储在字典中。若出现次数大于1，则为重复

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
class Solution:
    def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
        count = collection.Counters()
        ans = []
        def collect(node):
            if not node:
                return "#"
            serial = "{}, {}, {}".format(node.val, collect(node.left), collect(node.right))
            count[serial] += 1
            if count[serial] == 2:
                ans.append(node)
        collect(root)
        return serial

class Solution:
    def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
        hashmap = dict()
        self.dups = []
        self.serialize(root, hashmap)
        
        return self.dups
    def serialize(self, root, hashmap):
        if not node:
            return "#"
        s = str(root.val) + self.serialize(root.left, hashmap) + self.serialze(root.right, hashmap) #注意序列化是根左右， 左右根序列化会出问题，如testcase = [0,0,0,0,null,null,0,null,null,null,0]
        if not hashmap.get(s, 0):
            hashmap[s] = 0
        hashmap[s] += 1
        if hashmap[s] == 2:
            self.dups.append(node)
        return s

\653. Two Sum IV - Input is a BST

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:

1
2
3
4
5
6
7
8
9
10
Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

Output: True

Example 2:

1
2
3
4
5
6
7
8
9
10
Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 28

Output: False
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def __init__(self):
        self.s = set()
    def findTarget(self, root: TreeNode, k: int) -> bool:
        if not root:
            return False
        if (k-root.val) in self.s:
            return True
        else:
            self.s.add(root.val)
        return self.findTarget(root.left, k) or self.findTarget(root.right, k)

\654. Maximum Binary Tree

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

  1. The root is the maximum number in the array.
  2. The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
  3. 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:

1
2
3
4
5
6
7
8
9
10
Input: [3,2,1,6,0,5]
Output: return the tree root node representing the following tree:

      6
    /   \
   3     5
    \    / 
     2  0   
       \
        1

Note:

  1. The size of the given array will be in the range [1,1000].
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
        if len(nums) == 0:
            return None
        
        root = TreeNode(max(nums))
        i = nums.index(max(nums))
        root.left = self.constructMaximumBinaryTree(nums[:i])
        root.right = self.constructMaximumBinaryTree(nums[i+1: ])
        
        return root

思路二：单调栈

Intuition
We want to optimize from O(n^2) time complexity, O(nlogn) doesn’t seem like very promising, so we try O(n). Basically, if we need O(n) solution, we can only have constant operation during the traverse of the list. Therefore, we need something the keep track of the traversing memory. We then brainstorm several data structures that can help us keep track of this kind of memory.
What memory do we need? We need to remember the max node rather than trying to find them each time. So we need something that has an order and hierarchy. Stack comes in very naturally for this need given its characteristics. All we need to do is to force an order by ourselves.

Algorithm:
We keep track of a stack, and make sure the numbers in stack is in decreasing order.

For each new num, we make it into a TreeNode first.
Then:

  1. If stack is empty, we push the node into stack and continue
  2. If new value is smaller than the node value on top of the stack, we append TreeNode as the right node of top of stack.
  3. If new value is larger, we keep poping from the stack until the stack is empty OR top of stack node value is greater than the new value. During the pop, we keep track of the last node being poped.
    After step 2, we either in the situation of 0, or 1, either way, we append last node as left node of the new node.

After traversing, the bottom of stack is the root node because the bottom is always the largest value we have seen so far (during the traversing of list).

Space complexity:
Worst O(n) in the case that the list is sortedin descending order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def constructMaximumBinaryTree(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        if not nums:
            return None
        stk = []
        last = None
        for num in nums:
            while stk and stk[-1].val < nums:
                last = stk.pop()
            node = TreeNode(num)
            if stk:
                stk[-1].right = node
            if last:
                node.left = last
            stk.append(node)
            last = None
        return stk[0]

\655. Print Binary Tree

Print a binary tree in an m*n 2D string array following these rules:

  1. The row number m should be equal to the height of the given binary tree.
  2. The column number n should always be an odd number.
  3. The root node’s value (in string format) should be put in the exactly middle of the first row it can be put. The column and the row where the root node belongs will separate the rest space into two parts (left-bottom part and right-bottom part). You should print the left subtree in the left-bottom part and print the right subtree in the right-bottom part. The left-bottom part and the right-bottom part should have the same size. Even if one subtree is none while the other is not, you don’t need to print anything for the none subtree but still need to leave the space as large as that for the other subtree. However, if two subtrees are none, then you don’t need to leave space for both of them.
  4. Each unused space should contain an empty string "".
  5. Print the subtrees following the same rules.

Example 1:

1
2
3
4
5
6
7
Input:
     1
    /
   2
Output:
[["", "1", ""],
 ["2", "", ""]]

Example 2:

1
2
3
4
5
6
7
8
9
10
Input:
     1
    / \
   2   3
    \
     4
Output:
[["", "", "", "1", "", "", ""],
 ["", "2", "", "", "", "3", ""],
 ["", "", "4", "", "", "", ""]]

Example 3:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input:
      1
     / \
    2   5
   / 
  3 
 / 
4 
Output:

[["",  "",  "", "",  "", "", "", "1", "",  "",  "",  "",  "", "", ""]
 ["",  "",  "", "2", "", "", "", "",  "",  "",  "",  "5", "", "", ""]
 ["",  "3", "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]
 ["4", "",  "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]]

Note: The height of binary tree is in the range of [1, 10].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def printTree(self, root: TreeNode) -> List[List[str]]:
        def get_height(node):
            return 0 if not node else 1 + max(get_height(root.left), get_height(root.right))
        
        def update_output(root, row, left, right):
            if not node:
                return
            mid = (left + right) // 2
            self.output[row][mid] = str(node.val)
            update_output(node.left, row+1, left, mid-1)
            update_output(node.right, row+1, mid+1, right)
            
        height = get_height(root)
        width = 2 ** height - 1
        self.output = [[""] * width for _ in range(height)]
        update_output(root, 0, 0, width-1)
        
        return self.output

\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:

1
2
3
4
5
6
7
8
9
10
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:

1
2
3
4
5
6
7
8
9
10
Input: 

          1
         /  
        3    
       / \       
      5   3     

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

Example 3:

1
2
3
4
5
6
7
8
9
10
Input: 

          1
         / \
        3   2 
       /        
      5      

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

Example 4:

1
2
3
4
5
6
7
8
9
10
11
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.

思路：We know that a binary tree can be represented by an array (assume the root begins from the position with index 1 in the array). If the index of a node is i, the indices of its two children are 2*i and 2*i + 1. The idea is to use two arrays (start[] and end[]) to record the the indices of the leftmost node and rightmost node in each level, respectively. For each level of the tree, the width is end[level] - start[level] + 1. Then, we just need to find the maximum width.

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#DFS
class Solution:
    def widthOfBinaryTree(self, root: TreeNode) -> int:
        self.m = 1
        if not root:
            return 0
        start_of_level = []
        self.helper(root, 0, 1, start_of_level)
        return self.m
    def helper(self, root, level, index, l):
        if not root:
            return
        if level == len(l):
            l.append(index)
        self.m = max(self.m, index - l[level] + 1)
        self.helper(root.left, level+1, index*2, 1)
        self.helper(root.right, level+1, index*2+1, l) 
#BFS
class Solution:
    def widthOfBinaryTree(self, root: TreeNode) -> int:
        if not root:
            return 0
        cur = [root]
     	res = 1
        while len(cur) != 0:
            nxt = []
            for i in range(len(cur)):
                if not cur[i]:
                    nxt.append(None)
                    nxt.append(None)
                else:
                    nxt.append(cur[i].left)
                    nxt.append(cur[i].right)
            nxt = self.make_valid(nxt)
        	res = max(res, len(nxt))
            cur = nxt
        return res
    
    def make_valid(self, l):
        if not l:
            return []
        left, right = 0, len(l) - 1
        while(left<=right and l[left] == None):
            left += 1
        while(left<=right and l[right] == None):
            right += 1
        return l[left, right+1]